Recursion · 递归
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| 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à |
A definition that contains itself
- How do you say what an ancestor is? Your parent is an ancestor. So is your parent's ancestor. Those two sentences define an unbounded chain, and the second one uses the word it is defining.
- That is not a circular argument, because the first sentence gives the chain somewhere to stop. Without it, the definition would unwind for ever.
- Programs can be written the same way, and for problems shaped like that chain, a recursive 递归 solution is dramatically shorter than a loop.
- This lesson is the base case 基本情形 and the recursive case 递归情形, how a recursive call is traced, and what the call stack 调用栈 is doing underneath.
包含自己的定义
- 怎样说清什么是祖先?你的父母是祖先。你父母的祖先也是。这两句话定义了一条无限长的链,而第二句用了它正在定义的那个词。
- 这不是循环论证,因为第一句给了这条链一个停下来的地方。没有它,这个定义会永远展开下去。
- 程序也可以这样写,而对于形状像那条链的问题,递归(recursive)解法比循环短得多。
- 这一课讲基本情形(base case)和递归情形(recursive case)、怎样追踪一次递归调用,以及底层的调用栈(call stack)在做什么。
The two cases
- The base case is a version of the problem small enough to answer directly, with no further call. It is what stops the recursion.
- The recursive case calls the function again with a smaller input, moving towards the base case.
- Both are required. A recursion with no base case never stops; one whose input does not shrink never reaches the base case.
两种情形
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: · 每个递归算法都必须有一个基本情形,因为:
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. · 递归对自相似的问题(树、分治)是一个自然的契合,但每个调用增加一个栈帧——所以没有一个基本情形它会溢出栈。
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 all · 所有 that apply. · 递归例程要能终止,必须具备什么?选出所有适用的。
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. · 光有基本情形不够:如果输入永不缩小,基本情形永远到不了,栈帧会一直堆积直到栈溢出。
Worked example: trace a recursion
- Trace
Factorial(4). - Winding up:
Factorial(4)needs4 * Factorial(3), which needs3 * Factorial(2), which needs2 * Factorial(1). Nothing has been multiplied yet; each call is waiting. - Base case:
Factorial(1)returns 1 without calling anything. - Unwinding:
2 * 1 = 2is returned, then3 * 2 = 6, then4 * 6 = 24. - Show both directions. A trace that only goes down, or only comes back, loses half the marks.
例题:追踪一次递归
- 追踪
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. · 按调用实际完成的顺序逐步走过 fib(4):叶子(基本情形)先解决,然后每个父节点合并它的子节点。注意 fib(2) 被计算两次——那重复的工作就是为什么朴素的递归慢。
What does Factorial(4) return? · Factorial(4) 返回什么?
4 × 3 × 2 × 1 = 24. · 4 × 3 × 2 × 1 = 24。
What the machine is doing
- Every call needs its own copy of its parameters and local variables, because
Factorial(3)andFactorial(2)are different calls with different values ofn. - Those copies live in a stack frame 栈帧 on the call stack: one frame per call in progress, holding the parameters, the locals and the return address.
- A frame is pushed on each call and popped when it returns. That is why the values come back in the reverse of the order they were called: the call stack is a stack, exactly the ADT from topic 10.
机器在做什么
- 每次调用都需要自己的一份参数和局部变量,因为
Factorial(3)和Factorial(2)是n值不同的两次不同调用。 - 这些副本存放在调用栈上的一个栈帧(stack frame)里:每个进行中的调用一帧,保存参数、局部变量和返回地址。
- 调用时压入一帧,返回时弹出。这就是各个值按调用顺序的逆序回来的原因:调用栈就是栈,正是第 10 单元的那个抽象数据类型。
Put the events of evaluating Factorial(4) in order. · 把计算 Factorial(4) 的过程按顺序排列。
Nothing is multiplied on the way down; every call waits. The multiplications all happen as the stack unwinds. · 向下的路上什么乘法都没做;每个调用都在等待。所有乘法都发生在栈回收的过程中。
What goes wrong
- No base case, or a base case that is never reached: the recursion never stops, frames pile up, and the call stack runs out of memory. That is a stack overflow 栈溢出.
- Deep recursion: even a correct recursion of a million levels needs a million frames, so it can exhaust memory where a loop would use none.
- Repeated work: naive recursive Fibonacci recomputes the same values exponentially many times. Fix it with a loop, or with memoisation 记忆化, storing each result the first time it is computed.
会出什么问题
- 没有基本情形,或基本情形永远到不了:递归永不停止,栈帧不断堆积,调用栈耗尽内存。这就是栈溢出(stack overflow)。
- 递归太深:即使是正确的百万层递归也需要一百万个栈帧,所以它可能耗尽内存,而循环一点也不占。
- 重复计算:朴素的递归斐波那契会把同样的值重算指数多次。用循环修复它,或用记忆化(memoisation),第一次算出每个结果时就存起来。
Match each recursion term to what it means. · 把每个递归术语与它的含义配对。
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: · 一个函数调用的栈帧保存:
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. · 每个进行中的调用把它的参数和局部变量保存在调用栈上自己的____里。
Pushed on call, popped on return. That is why values come back in the reverse of the order the calls were made. · 调用时压入,返回时弹出。这就是各个值按调用顺序的逆序回来的原因。
Recursion or iteration
- Recursion suits self-similar problems, where the problem contains a smaller copy of itself: tree traversal, divide and conquer such as binary search and merge sort, and the ancestor chain above.
- Iteration suits everything else, and uses no extra memory for the repetition.
- Anything recursive can be written iteratively and the reverse is also true. The choice is about which one expresses the problem clearly, weighed against the memory the stack costs.
递归还是迭代
- 递归适合自相似的问题——问题内部包含它自己的一个更小副本:树的遍历、二分查找和归并排序这样的分治,以及上面那条祖先链。
- 迭代适合其余一切,而且重复本身不占额外内存。
- 任何递归都能写成迭代,反过来也成立。选择在于哪一种把问题表达得更清楚,再权衡栈所花的内存。
A recursive routine crashes with a stack overflow. Which explanation is correct? · 一个递归例程以栈溢出崩溃。哪个解释是正确的?
Stack overflow is about frames, not arithmetic. A number too large for its register is an arithmetic overflow, a different thing entirely. · 栈溢出关乎栈帧,不是算术。一个数大到寄存器装不下是算术溢出,完全是另一回事。
Worked example: state the risks
- A student writes a recursive routine and it crashes with a stack overflow. Give two possible causes.
- There is no base case, or the base case can never be reached because the input does not get smaller on each call, so calls continue for ever and frames accumulate.
- The recursion is correct but too deep: each of the very many calls keeps its own stack frame, and the call stack runs out of memory before the base case is reached.
- Both causes are about frames accumulating. Say what accumulates and why it never stops.
例题:说出风险
- 一名学生写了一个递归例程,它以栈溢出崩溃。给出两个可能的原因。
- 没有基本情形,或者基本情形永远到不了——因为每次调用时输入没有变小——于是调用无休止地继续,栈帧不断累积。
- 递归是正确的但太深:那非常多的调用每一个都保留自己的栈帧,在到达基本情形之前调用栈就耗尽了内存。
- 两个原因都是关于栈帧累积的。要说出累积的是什么,以及为什么它停不下来。
Marks that slip away
- A recursion needs both a base case and an input that gets smaller. Naming only the base case is half the condition.
- In a trace, show the calls winding up and the values unwinding. Both directions carry marks.
- Each call has its own parameters and locals, in its own stack frame. That is why recursion costs memory that iteration does not.
- Stack overflow is running out of stack memory from too many frames, not an arithmetic overflow.
容易丢掉的分
- 递归需要同时有基本情形和会变小的输入。只说基本情形只是一半的条件。
- 追踪时要写出调用的向下展开和值的向上回收。两个方向都有分。
- 每次调用都有自己的参数和局部变量,存在自己的栈帧里。这就是递归要花掉迭代不花的内存的原因。
- 栈溢出是栈帧太多耗尽了栈内存,不是算术溢出。
You've got it
- a recursive routine needs a base case solved directly and a recursive case that calls itself with a smaller input
- trace it in both directions: calls winding up to the base case, then values unwinding back
- each call has its own stack frame on the call stack, pushed on call and popped on return, which is why recursion costs memory
- risks: no reachable base case gives infinite recursion and stack overflow, deep recursion exhausts memory, and repeated work needs a loop or memoisation
你掌握了
- 递归例程需要一个可直接求解的基本情形,和一个用更小输入调用自己的递归情形
- 两个方向都要追踪:调用一路向下展开到基本情形,再把值一路回收
- 每次调用在调用栈上有自己的栈帧,调用时压入、返回时弹出,这就是递归要花内存的原因
- 风险:没有可达的基本情形会导致无限递归和栈溢出,过深的递归耗尽内存,重复计算需要循环或记忆化