A recursive subroutine is one that calls itself. Recursion solves a problem by reducing it to a smaller version of the same problem, until it reaches one simple enough to answer directly.
Base case and general case
Every correct recursive function has two parts:
- Base case: a situation where it returns an answer without calling itself. It stops the recursion.
- General (recursive) case: it calls itself with a smaller or simpler input that moves towards the base case.
Without a base case, or if the input never gets closer to it, the calls never stop and the program crashes with a stack overflow.
Factorial: n! = n x (n-1)!, with 0! = 1.
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 THEN
RETURN 1
ELSE
RETURN n * Factorial(n - 1)
ENDIF
ENDFUNCTION
Tracing Factorial(3):
Factorial(3) = 3 * Factorial(2)
= 3 * (2 * Factorial(1))
= 3 * (2 * (1 * Factorial(0)))
= 3 * 2 * 1 * 1 = 6
The call stack
Each call gets a stack frame holding its parameters, local variables and return address. Calls are pushed on the stack as they go deeper (winding), and popped as each returns a value (unwinding). Deep recursion uses a lot of memory.
More examples
Fibonacci: each number is the sum of the previous two.
FUNCTION Fib(n : INTEGER) RETURNS INTEGER
IF n <= 1 THEN
RETURN n
ELSE
RETURN Fib(n - 1) + Fib(n - 2)
ENDIF
ENDFUNCTION
This is easy to write but slow, as it repeats the same calculations many times.
Recursion suits problems that are naturally self-similar: tree traversals, binary search, merge sort, quicksort and the Towers of Hanoi.
Recursion versus iteration
| Feature | Recursion | Iteration |
|---|---|---|
| Code | Short, elegant | Often longer |
| Memory | Uses stack frames | Uses little |
| Speed | Slower (call overhead) | Faster |
| Risk | Stack overflow | Infinite loop |
Any recursive solution can be rewritten with loops and an explicit stack, and any loop can be written recursively. Choose recursion when it makes the problem clearer.
Check your understanding
What is the purpose of a base case?
- To stop the recursion
- To start the program
- To declare variables
- To loop forever
Answer: To stop the recursion. It returns a result without another call.
What happens if a recursive function has no reachable base case?
- It returns 0
- Stack overflow
- It runs once
- It sorts the data
Answer: Stack overflow. The call stack fills up.
What is Factorial(4)?
- 10
- 16
- 24
- 12
Answer: 24. 4 x 3 x 2 x 1 = 24.
Where are return addresses and parameters stored during recursion?
- In the call stack as stack frames
- In the hard disk
- In the ALU
- In ROM
Answer: In the call stack as stack frames. They are removed as calls return.
