B2.4.5 · Programming algorithms
Tracing recursive algorithms
By the end you can
Trace recursive algorithms through call stack frame allocation (winding) and return value resolution (unwinding).
Tracing recursion requires tracking two distinct phases: the winding phase (where calls multiply and stack frames accumulate) and the unwinding phase (where base cases return and frames pop in reverse order).
Tracing the call stack#
Whenever a function calls itself, the computer pauses execution of the current frame, preserves all local variables, and pushes a brand-new onto the call stack.
Consider calculating $4!$ (factorial of 4):
fact(4)pauses, waiting for4 * fact(3).fact(3)pauses, waiting for3 * fact(2).fact(2)pauses, waiting for2 * fact(1).fact(1)hits the base case and returns1immediately!- Unwinding begins:
fact(2)evaluates $2 \times 1 = 2$ and returns. fact(3)evaluates $3 \times 2 = 6$ and returns.fact(4)evaluates $4 \times 6 = 24$ and returns the final answer.
Step 1 of 8: Push fact(4) onto call stack. Calls fact(3)
Stack Depth: 1Call Stack (Top of Stack = Currently Active Activation Record)
Check yourself
Recursive tracing
Quick questions, made fresh every time and marked here. Do a few until they feel easy.
Exam practice
Paper 1-style questions
3 questions · 8 marks
Write your answer as you would in the exam, then show the mark points and tick each one your answer made. These are our own questions in the style of the exam, not past-paper questions.
1.Trace the execution of fib(4) given the recursive definition, stating the total number of calls and final return value.
[4]Trace: Follow the program or process step by step, recording the values.
2.Explain what happens during the 'unwinding' phase of a recursive algorithm.
[2]Explain: Give reasons: say what happens AND why, or how one thing causes another.
3.Describe how the call stack grows and shrinks during a recursive factorial calculation.
[2]Describe: A detailed account: say what happens, step by step if it is a process.
In a nutshell
- Recursive tracing involves a winding phase (accumulating stack frames) and an unwinding phase (returning values in LIFO order).
- Each recursive call creates an activation record on the call stack storing parameters, local variables and return addresses.
- Complex recursive calls like Fibonacci create tree-structured branching traces with exponential function invocations.
- Draw a call-tree diagram or trace table to track return values during the unwinding phase of recursive tracing.