Recursion is a programming technique in which a subprogram calls itself to solve a smaller version of the same problem. It works only when there is a reachable base case that stops further calls and a recursive case that reduces the problem toward that base case.
How recursion works
Each recursive call creates a new stack frame on the call stack. This frame stores information such as argument values, local variables, and the return address.
A recursive algorithm therefore follows these steps:
- Test whether the base case has been reached.
- If not, call the subprogram with a smaller input.
- Suspend the current call.
- After the base case returns, complete suspended calls in reverse order, called unwinding the call stack.
For example:
FUNCTION factorial(n)
IF n = 0 THEN
RETURN 1
ELSE
RETURN n * factorial(n - 1)
END IF
END FUNCTION
For factorial(3):
factorial(3), factorial(2), factorial(1), factorial(0)
The base case returns 1; unwinding then produces 1, 2, and 6. Therefore, .
| Phase | What happens |
|---|---|
| Recursive descent | New calls and stack frames are created. |
| Base case | No further recursive call is made. |
| Stack unwinding | Calls return results in reverse order. |
For this factorial algorithm, both the time complexity and auxiliary space complexity are . Deep recursion can cause a stack overflow because memory is required for every active call.
A common misconception is that recursion automatically repeats forever. It does so only if the base case is missing, unreachable, or the recursive argument does not progress toward it.
Exam technique
For an IB B2.4 trace question, show every recursive call, identify the base case, and then show the returned values during unwinding. For an explain question, connect self-calls explicitly to stack-frame creation and termination rather than merely stating that the function “repeats.”
