Recursion
| English | Chinese | Pinyin |
|---|---|---|
| recursive | 递归 | dì guī |
| base case | 基本情形 | jī běn qíng xíng |
| recursive case | 递归情形 | dì guī qíng xíng |
| call stack | 调用栈 | diào yòng zhàn |
| stack overflow | 栈溢出 | zhàn yì chū |
| memoisation | 记忆化 | jì yì huà |
| stack frame | 栈帧 | zhàn zhēn |
A function that calls itself
- A recursive 递归 algorithm calls itself with a smaller version of the same problem.
- It needs a base case 基本情形 to stop, and a recursive case 递归情形 that shrinks the input.
- The compiler handles it with the call stack 调用栈.
Base case and recursive case
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 small enough to solve directly — without it the recursion never stops.
- The recursive case reduces the input and calls itself.
- Recursion suits self-similar problems: trees, divide-and-conquer (binary search, merge sort).
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.
What does Factorial(4) return?
4 × 3 × 2 × 1 = 24.
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.
Tracing and risks
Factorial(4)calls down toFactorial(1)=1, then unwinds:2*1=2,3*2=6,4*6=24.- Risks: a missing base case → infinite recursion → stack overflow 栈溢出; deep recursion uses lots of memory; repeating work is slow (naive Fibonacci is exponential — use a loop or memoisation 记忆化).
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.
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.
What the compiler does
- Each call needs its own copy of its parameters and local variables, kept on the call stack.
- For each call the compiler pushes a stack frame 栈帧 holding the parameters, local variables, and the return address (where to resume in the caller).
- On return, the value is handed back and the frame is popped. This is the same mechanism as ordinary calls — there's no special "recursion mechanism", which is why deep recursion can overflow the stack.
Each recursive call pushes a stack frame; the stack unwinds as each call returns its value
- Recursive algorithms call themselves until a base case, then return values while unwinding.
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.
You've got it
- recursion = base case (stops it) + recursive case (shrinks the input and calls itself)
- a missing base case → infinite recursion → stack overflow
- each call gets a stack frame (parameters, locals, return address) on the call stack
- suits self-similar / divide-and-conquer problems; a loop is cleaner otherwise