Recursion · 递归
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · 此页面需较新浏览器（支持 SharedArrayBuffer）。请升级 Chrome、Edge、Firefox 或 Safari 至最新版本。
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.
中文
调用自己的函数
- 递归(recursion)就是一个函数调用它自己。
- 每次调用都应处理这个问题的一个更小的版本。
- 做对了的话,问题会不断缩小,直到简单到可以直接解决。
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).
中文
基本情形与递归情形
- 基本情形(base case)是最简单的情形 —— 它让递归停下来。
- 递归情形(recursive case)在更小的输入上再次调用这个函数。
- 没有基本情形,函数就永远停不下来(会出错)。
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.
中文
一个例子:阶乘
- 阶乘
n!表示n × (n-1) × ... × 1。 - 用递归形式表示:
n! = n × (n-1)!,基本情形是0! = 1。 - 每次调用都把
n乘上小一号的阶乘。
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.
中文
计算机是怎么运行它的
- 每次调用在等待内层调用时,都被暂存在调用栈(call stack)上。
- 当基本情形返回后,被暂停的调用会一个接一个地完成。
- 调用太多会让栈溢出 —— Python 会抛出
RecursionError。
English
In Cambridge pseudocode
- A recursive function names its base case and recursive case clearly.
中文
用剑桥伪代码表示
- 递归函数会清楚地写明它的基本情形和递归情形。
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.
中文
常见错误
- 每个递归都要有基准情形,否则会撑爆调用栈。
- 每次调用都要更靠近基准情形。
English
Now you try
- Give each function a base case and a recursive case.
- Press Check answer to test your code.
中文
现在轮到你
- 给每个函数都写好一个基本情形和一个递归情形。
- 按检查答案来测试你的代码。
Explore · 探索
Recursion returns from the leaves · 递归从叶子往上返回
Each call splits into smaller calls; answers return up from the base cases. · 每次调用都分成更小的调用;答案从基线情形往上返回。
Write a recursive sum_to(n) that returns 1 + 2 + ... + n. The base case is sum_to(0) which is 0. · 编写一个递归的 sum_to(n),返回 1 + 2 + ... + n。基本情形是 sum_to(0),结果为 0。
Click Run to see the output here. · 点击“运行”查看此处输出。
Write a recursive power(base, exp) that returns base raised to exp. The base case is exp == 0, which gives 1. · 编写一个递归的 power(base, exp),返回 base 的 exp 次方。基本情形是 exp == 0,结果为 1。
Click Run to see the output here. · 点击“运行”查看此处输出。
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 []. · 编写一个递归的 count_up(n),返回列表 [1, 2, ..., n]。基本情形是 count_up(0),结果为空列表 []。
Click Run to see the output here. · 点击“运行”查看此处输出。