Recursion
Trang này cần trình duyệt gần đây (hỗ trợ SharedArrayBuffer). Vui lòng cập nhật Chrome, Edge, Firefox hoặc Safari lên phiên bản mới nhất.
Một hàm gọi chính nó
- Đệ quy là khi một hàm gọi chính nó.
- Mỗi lần gọi nên xử lý một phiên bản nhỏ hơn của vấn đề.
- Khi thực hiện đúng, vấn đề sẽ thu nhỏ lại cho đến khi trở nên quá đơn giản để giải quyết.
Trường hợp cơ sở và trường hợp đệ quy
- Trường hợp cơ sở là trường hợp đơn giản nhất — nó dừng quá trình đệ quy.
- Trường hợp đệ quy gọi lại hàm đó với một đầu vào nhỏ hơn.
- Nếu không có trường hợp cơ sở, hàm sẽ không bao giờ dừng (lỗi).
English
def countdown(n):
if n == 0:
print("Go!")
return
print(n)
countdown(n - 1)
countdown(3)
Ví dụ minh họa: Số nhân thừa
- Số nhân thừa
n!có nghĩa làn × (n-1) × ... × 1. - Ở dạng đệ quy:
n! = n × (n-1)!, và trường hợp cơ sở là0! = 1. - Mỗi lần gọi nhân
nvới số nhân thừa của một số ít hơn một.
English
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(4))
Máy tính chạy nó như thế nào
- Mỗi lần gọi bị tạm dừng trên ngân hàng gọi trong khi chờ đợi cuộc gọi nội bộ.
- Khi trường hợp cơ sở trả về, các cuộc gọi bị tạm dừng sẽ hoàn thành lần lượt.
- Quá nhiều lần gọi làm tràn ngân hàng gọi — Python sẽ báo lỗi
RecursionError.
Trong pseudocode Cambridge
- Một hàm đệ quy nên đặt tên rõ ràng cho trường hợp cơ sở và trường hợp đệ quy.
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 THEN
RETURN 1 // base case
ELSE
RETURN n * Factorial(n - 1) // recursive case
ENDIF
ENDFUNCTION
Lỗi thường gặp
- Mọi đệ quy đều cần một trường hợp cơ sở, nếu không sẽ làm tràn ngân hàng gọi.
- Mỗi lần gọi phải tiến gần hơn đến trường hợp cơ sở.
Bây giờ bạn thử
- Hãy gán cho mỗi hàm một trường hợp cơ sở và một trường hợp đệ quy.
- Nhấn Check answer (Kiểm tra câu trả lời) để thử mã của bạn.
Khám phá
đệ quy trả về từ các lá
Mỗi lời gọi chia thành các lời gọi nhỏ hơn; câu trả lời trả về lên từ các trường hợp cơ sở.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Viết một hàm đệ quy sum_to(n) trả về 1 + 2 + ... + n. Trường hợp cơ sở là sum_to(0) bằng 0.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Viết một hàm đệ quy power(base, exp) trả về base lũy thừa exp. Trường hợp cơ sở là exp == 0, trả về 1.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Viết một hàm đệ quy count_up(n) trả về danh sách [1, 2, ..., n]. Trường hợp cơ sở là count_up(0) chính là danh sách rỗng [].
Nhấn Chạy để xem kết quả ở đây.