| English | 释义 | 拼音 |
|---|---|---|
| recursive/rɪˈkɜːsɪv/ | 递归 | dì guī |
| base case/beɪs keɪs/ | 基本情形 | jī běn qíng xíng |
| recursive case/rɪˈkɜːsɪv keɪs/ | 递归情形 | dì guī qíng xíng |
| call stack/kɔːl stæk/ | 调用栈 | diào yòng zhàn |
| stack frame/stæk freɪm/ | 栈帧 | zhàn zhēn |
| stack overflow/stæk ˌəʊvəˈfləʊ/ | 栈溢出 | zhàn yì chū |
| memoisation/ˌmeməʊaɪˈzeɪʃn/ | 记忆化 | jì yì huà |
包含自己的定义
- 怎样说清什么是祖先?你的父母是祖先。你父母的祖先也是。这两句话定义了一条无限长的链,而第二句用了它正在定义的那个词。
- 这不是循环论证,因为第一句给了这条链一个停下来的地方。没有它,这个定义会永远展开下去。
- 程序也可以这样写,而对于形状像那条链的问题,递归(recursive)解法比循环短得多。
- 这一课讲基本情形(base case)和递归情形(recursive case)、怎样追踪一次递归调用,以及底层的调用栈(call stack)在做什么。
两种情形
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 OR n = 1 THEN
RETURN 1 // 基本情形
ELSE
RETURN n * Factorial(n - 1) // 递归情形
ENDIF
ENDFUNCTION
- 基本情形是这个问题小到可以直接回答的版本,不再进一步调用。它是让递归停下来的东西。
- 递归情形用一个更小的输入再次调用这个函数,朝基本情形靠近。
- 两者都必须有。没有基本情形的递归永不停止;输入不缩小的递归永远到不了基本情形。
Every recursive algorithm must have a base case because:
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
The base case is the condition that ends the chain of calls; without it the recursion runs forever.
Recursion is a natural fit for self-similar problems (trees, divide-and-conquer), but each call adds a stack frame — so without a base case it overflows the stack.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
A simple counting loop is cleaner for plain iteration; recursion shines when the problem contains smaller copies of itself.
What must a recursive routine have to terminate? Select 所有 that apply.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
A base case alone is not enough: if the input never shrinks, the base case is never reached and frames pile up until the stack overflows.
例题:追踪一次递归
- 追踪
Factorial(4)。 - 向下展开:
Factorial(4)需要4 * Factorial(3),它需要3 * Factorial(2),它又需要2 * Factorial(1)。此时还没有做任何乘法;每个调用都在等待。 - 基本情形:
Factorial(1)不调用任何东西,直接返回 1。 - 向上回收:返回
2 * 1 = 2,再3 * 2 = 6,再4 * 6 = 24。 - 两个方向都要写出来。只往下走、或只往回走的追踪会丢掉一半的分。
Recursion unwinds from the leaves up
Step through fib(4) in the order the calls actually finish: the leaves (base cases) resolve first, then each parent combines its children. Notice fib(2) is computed twice — that repeated work is why naive recursion is slow.
What does Factorial(4) return?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
4 × 3 × 2 × 1 = 24.
机器在做什么
- 每次调用都需要自己的一份参数和局部变量,因为
Factorial(3)和Factorial(2)是n值不同的两次不同调用。 - 这些副本存放在调用栈上的一个栈帧(stack frame)里:每个进行中的调用一帧,保存参数、局部变量和返回地址。
- 调用时压入一帧,返回时弹出。这就是各个值按调用顺序的逆序回来的原因:调用栈就是栈,正是第 10 单元的那个抽象数据类型。
Put the events of evaluating Factorial(4) in order.
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
Nothing is multiplied on the way down; every call waits. The multiplications all happen as the stack unwinds.
会出什么问题
- 没有基本情形,或基本情形永远到不了:递归永不停止,栈帧不断堆积,调用栈耗尽内存。这就是栈溢出(stack overflow)。
- 递归太深:即使是正确的百万层递归也需要一百万个栈帧,所以它可能耗尽内存,而循环一点也不占。
- 重复计算:朴素的递归斐波那契会把同样的值重算指数多次。用循环修复它,或用记忆化(memoisation),第一次算出每个结果时就存起来。
Match each recursion term to what it means.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
A recursion needs a base case to stop and a recursive case to shrink the problem; each call adds a stack frame.
A stack frame for a function call holds:
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Each frame stores that call's parameters, locals and where to resume — so calls don't trample each other.
Each call in progress keeps its parameters and locals in its own ____ on the call stack.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Pushed on call, popped on return. That is why values come back in the reverse of the order the calls were made.
递归还是迭代
- 递归适合自相似的问题——问题内部包含它自己的一个更小副本:树的遍历、二分查找和归并排序这样的分治,以及上面那条祖先链。
- 迭代适合其余一切,而且重复本身不占额外内存。
- 任何递归都能写成迭代,反过来也成立。选择在于哪一种把问题表达得更清楚,再权衡栈所花的内存。
A recursive routine crashes with a stack overflow. Which explanation is correct?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Stack overflow is about frames, not arithmetic. A number too large for its register is an arithmetic overflow, a different thing entirely.
例题:说出风险
- 一名学生写了一个递归例程,它以栈溢出崩溃。给出两个可能的原因。
- 没有基本情形,或者基本情形永远到不了——因为每次调用时输入没有变小——于是调用无休止地继续,栈帧不断累积。
- 递归是正确的但太深:那非常多的调用每一个都保留自己的栈帧,在到达基本情形之前调用栈就耗尽了内存。
- 两个原因都是关于栈帧累积的。要说出累积的是什么,以及为什么它停不下来。
容易丢掉的分
- 递归需要同时有基本情形和会变小的输入。只说基本情形只是一半的条件。
- 追踪时要写出调用的向下展开和值的向上回收。两个方向都有分。
- 每次调用都有自己的参数和局部变量,存在自己的栈帧里。这就是递归要花掉迭代不花的内存的原因。
- 栈溢出是栈帧太多耗尽了栈内存,不是算术溢出。
你掌握了
- 递归例程需要一个可直接求解的基本情形,和一个用更小输入调用自己的递归情形
- 两个方向都要追踪:调用一路向下展开到基本情形,再把值一路回收
- 每次调用在调用栈上有自己的栈帧,调用时压入、返回时弹出,这就是递归要花内存的原因
- 风险:没有可达的基本情形会导致无限递归和栈溢出,过深的递归耗尽内存,重复计算需要循环或记忆化