This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · 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.
English
A function that calls itself
- Recursion is when a function calls itself.
- Each call should work on a smaller version of the problem.
- Done right, the problem shrinks until it is trivial to solve.
Tiếng Việ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.
English
Base case and recursive case
- The base case is the simplest case — it stops the recursion.
- The recursive case calls the function again on a smaller input.
- Without a base case the function never stops (an error).
Tiếng Việ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).
def countdown(n):
if n == 0:
print("Go!")
return
print(n)
countdown(n - 1)
countdown(3)
English
A worked example: factorial
- The factorial
n!meansn × (n-1) × ... × 1. - In recursive form:
n! = n × (n-1)!, and the base case is0! = 1. - Each call multiplies
nby the factorial of one less.
Tiếng Việt
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.
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(4))
English
How the computer runs it
- Each call is paused on a call stack while it waits for the inner call.
- When the base case returns, the paused calls finish one by one.
- Too many calls overflow the stack — Python raises a
RecursionError.
Tiếng Việt
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.
English
In Cambridge pseudocode
- A recursive function names its base case and recursive case clearly.
Tiếng Việt
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
English
Common mistakes
- Every recursion needs a base case, or it overflows the call stack.
- Each call must move closer to the base case.
Tiếng Việt
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ở.
English
Now you try
- Give each function a base case and a recursive case.
- Press Check answer to test your code.
Tiếng Việt
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.
Explore · Khám phá
Recursion returns from the leaves · đệ quy trả về từ các lá
Each call splits into smaller calls; answers return up from the base cases. · 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ở.
Write a recursive sum_to(n) that returns 1 + 2 + ... + n. The base case is sum_to(0) which is 0. · 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.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Write a recursive power(base, exp) that returns base raised to exp. The base case is exp == 0, which gives 1. · 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.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Write a recursive count_up(n) that returns the list [1, 2, ..., n]. The base case is count_up(0) which is the empty list []. · 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 [].
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.