| English | 意味 |
|---|---|
| recursive/rɪˈkɜːsɪv/ | 再帰的 |
| base case/beɪs keɪs/ | 基底ケース |
| recursive case/rɪˈkɜːsɪv keɪs/ | 再帰ケース |
| call stack/kɔːl stæk/ | 呼び出しスタック |
| stack frame/stæk freɪm/ | スタックフレーム |
| stack overflow/stæk ˌəʊvəˈfləʊ/ | スタックオーバーフロー |
| memoisation/ˌmeməʊaɪˈzeɪʃn/ | メモ化 |
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:
難易度 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 all 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.
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?
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
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.
難易度 3/5 · 200 コイン + 今日初回完了時に小ボーナス付与
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.
難易度 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.
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?
難易度 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.
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