Recursion
Introduced| English | Meaning |
|---|---|
| recursive/rɪˈkɜːsɪv/ | Defined in terms of earlier values or smaller instances of the same process. |
| base case/beɪs keɪs/ | A version of the problem small enough to answer directly, with no further call. |
| recursive case/rɪˈkɜːsɪv keɪs/ | The part of a recursive definition or algorithm that reduces a problem by invoking the same process on a smaller or simpler case. |
| call stack/kɔːl stæk/ | A stack that records active function calls and their return information. |
| stack frame/stæk freɪm/ | An area of a call stack holding information for one routine invocation, such as parameters, local variables and return information. |
| stack overflow/stæk ˌəʊvəˈfləʊ/ | A condition in which a program needs more call-stack space than is available, often because of excessive recursion. |
| memoisation/ˌmeməʊaɪˈzeɪʃn/ | Saving the results of function calls so repeated calls with the same inputs can reuse an earlier result. |
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.
The two cases
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 OR n = 1 THEN
RETURN 1 // base case
ELSE
RETURN n * Factorial(n - 1) // recursive case
ENDIF
ENDFUNCTION
- 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.
Every recursive algorithm must have a base case because:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
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.
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?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
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.
Put the events of evaluating Factorial(4) in order.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
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.
Match each recursion term to what it means.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
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:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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