Gọi lại chính hàm với dữ liệu tiến về điểm dừng
Hàm đệ quy có lời gọi đến chính nó. Lời gọi ấy cần dẫn đến trường hợp cơ sở để quá trình kết thúc.
Xét n là số nguyên không âm. Hàm sau in từ n xuống1; mỗi số ở một dòng.
```python
def dem_lui(n):
if n > 0:
print(n)
dem_lui(n - 1)
```
`dem_lui(3)` in 3 rồi gọi `dem_lui(2)`, tiếp tục in 2, in 1. Khi n=0, điều kiện n>0 sai nên không in và không gọi tiếp. Đó là trường hợp cơ sở của cách viết này; không bắt buộc phải có một nhánh else riêng.
Đổi vị trí print làm đổi thứ tự in
Vẫn giảm n qua từng lời gọi nhưng đặt print sau lời gọi:
```python
def dem_xuoi(n):
if n > 0:
dem_xuoi(n - 1)
print(n)
```
Với n=3, hàm đi tới n=0 trước. Sau đó lời gọi n=1 tiếp tục và in 1; lời gọi n=2 in 2; lời gọi n=3 in 3.
| Lời gọi ban đầu | Thứ tự các n khi gọi sâu hơn | Thứ tự in |
|---|---|---|
| dem_lui(3) | 3→2→1→0 | 3, 2, 1 |
| dem_xuoi(3) | 3→2→1→0 | 1, 2, 3 |
Hai hàm chỉ in, không có return kèm giá trị; kết quả trả về của chúng là None. Các số trên màn hình không tự trở thành giá trị trả về.
Để thử, thêm dòng `dem_xuoi(3)` dưới phần định nghĩa rồi chạy bằng Python3. Thử với 0 thì không có số nào được in; thử với 100 thì nhận các số từ 1 đến 100, mỗi số một dòng.
Có nhánh dừng nhưng phải đi tới được nhánh ấy
Nếu bỏ điều kiện n>0, hàm tiếp tục gọi với 0,−1,−2,… mà không có điểm dừng theo chương trình. Python có thể báo **RecursionError** khi vượt giới hạn độ sâu đệ quy; không xem lỗi đó là cơ sở đúng của thuật toán.
Ngược lại, chỉ thêm nhánh `if n == 0` chưa đủ nếu lời gọi tiếp theo vẫn giữ nguyên n. Cần kiểm cả trường hợp cơ sở lẫn cách thay đổi dữ liệu để lời gọi thực sự tiến về cơ sở. Trong ví dụ trên, n giảm1 từ một số nguyên không âm.
Bài luyện
Với hàm dem_lui trong bài, dem_lui(0) làm gì?
Lời gọi tiếp chỉ nằm trong nhánh n>0.
Điều kiện0>0 sai nên thân if không chạy.
Đó là hành vi khi bỏ điều kiện bảo vệ.
Không có lệnh in 1 ở trường hợp0.
Lời giải
Ở n=0, điều kiện n>0 sai. Hàm đi tới cuối mà không in và không gọi lại; đây là điểm dừng. Giá trị trả về là None.
Bài luyện
Với hàm dem_xuoi trong bài, dem_xuoi(3) in các số theo thứ tự nào?
Trường hợp n=0 không chạy thân if.
Mỗi lời gọi dùng một n khác nhau.
Print chạy sau khi lời gọi với n−1 hoàn tất.
Đó là thứ tự khi print nằm trước lời gọi.
Lời giải
Hàm gọi sâu tới n=0 rồi trở lại. Lời gọi n=1 in 1 trước, tiếp đến n=2 in 2 và n=3 in 3; số 0 không được in.
Bài luyện
Một hàm có nhánh dừng khi n==0; với n>0 lại gọi chính nó bằng cùng n. Khi bắt đầu n=3, vì sao cách viết đó chưa đúng?
Điều kiện cần được đạt tới trong quá trình thực hiện.
Tham số không tự đổi nếu không viết phép thay đổi.
Không có quy tắc buộc cơ sở phải đặt sau lời gọi.
Nhánh dừng tồn tại nhưng không được đi tới từ3.
Lời giải
Lời gọi3 dẫn tới lời gọi3 khác, rồi tiếp tục như vậy. Muốn dừng ở0 phải thay đổi đối số theo cách đạt được0, chẳng hạn n−1 trong bài đếm với đầu vào nguyên không âm.
Đang học