To trace a recursive algorithm, follow each call until the base case is reached, recording every call as a separate stack frame. Then work backwards through the calls, calculating each returned value as the call stack unwinds.
A recursive algorithm solves a problem by calling itself with a smaller or simpler input. Every correct recursive algorithm needs a base case that terminates the recursion and a recursive case that moves the input towards that base case.
Consider this factorial algorithm:
FUNCTION factorial(n)
IF n = 0
RETURN 1
ELSE
RETURN n * factorial(n - 1)
END IF
END FUNCTION
To trace factorial(4), separate the process into the calling phase and the returning phase:
| Step | Call stack or return value |
|---|---|
| Call 1 | factorial(4) waits for factorial(3) |
| Call 2 | factorial(3) waits for factorial(2) |
| Call 3 | factorial(2) waits for factorial(1) |
| Call 4 | factorial(1) waits for factorial(0) |
| Base case | factorial(0) returns 1 |
| Return 1 | factorial(1) returns 1 * 1 = 1 |
| Return 2 | factorial(2) returns 2 * 1 = 2 |
| Return 3 | factorial(3) returns 3 * 2 = 6 |
| Return 4 | factorial(4) returns 4 * 6 = 24 |
Each unfinished call remains on the call stack with its own parameter value. The most recent call returns first, so recursion follows last in, first out (LIFO) behaviour.
A common misconception is to calculate each multiplication immediately during the calling phase. This is incorrect because the recursive call must return a value before the multiplication can be completed.
For an IB Computer Science HL trace question, show the parameter value for every call, identify the base case, and record return values in reverse order. Do not give only the final output; examiners may award marks for the intermediate stack frames and correct unwinding process.
