How do I trace multiple recursive calls in one line, like Fibonacci?

Trace them strictly depth-first. Fully resolve the left recursive call down to its base cases and get its return value before initiating the right recursive call, matching standard program counter execution.

What if the function has no return value (void)?

Track the side effects, such as print statements or array mutations, sequentially in your global state column as each frame executes or resumes.

How do I handle arrays or objects passed by reference?

Maintain a single representation of the array in the global state column. Any stack frame that modifies the array updates this single reference immediately.

How to trace a recursive function by hand

Tracing a recursive function by hand requires explicitly modeling the call stack to track the state of each active function invocation. This method applies whenever you need to determine the output, state changes, or complexity of an algorithm that calls itself.

By drawing a distinct stack frame for every invocation, you isolate local variables and prevent confusion between distinct recursive calls.

The setup

Prepare a physical or digital workspace divided into two columns: one for the active call stack and one for output or global state changes. Write the initial function call at the bottom of the stack column, representing the bottom of the call stack.

The steps

Write the current function call with its evaluated argument values in a new frame.
Execute the function body line by line.
If a recursive call is reached, mark the current line, pause the current function, and draw a new stack frame above it with the new arguments.
When a base case is reached, record its return value and cross out its stack frame.
Substitute the return value into the paused calling function and resume its execution from the marked line.
Repeat until the initial call at the bottom of the stack returns.

Checking the result

Verify that every pushed stack frame has exactly one corresponding pop or return. Ensure that local variables within a frame were strictly isolated and not accidentally overwritten by operations in subsequent recursive calls.

Common errors

Failing to pause the calling function and continuing its execution before the recursive call returns. Overwriting local variables across different stack frames. Forgetting to substitute the return value back into the exact expression that triggered the call.

Worked example

Trace the execution of $f(3)$ for the following function:

$f(n) = 1$ if $n \le 1$ $f(n) = n imes f(n-1)$ if $n > 1$

Call 1 (Bottom of stack): $f(3)$ . $n = 3$ . Since $3 > 1$ , evaluate $3 imes f(2)$ . Pause $f(3)$ at $3 imes f(2)$ . Push $f(2)$ .

Call 2: $f(2)$ . $n = 2$ . Since $2 > 1$ , evaluate $2 imes f(1)$ . Pause $f(2)$ at $2 imes f(1)$ . Push $f(1)$ .

Call 3 (Top of stack): $f(1)$ . $n = 1$ . Since $1 \le 1$ , base case reached. Return 1. Pop $f(1)$ .

Resume Call 2: $f(2)$ . Substitute return value: $2 imes 1 = 2$ . Return 2. Pop $f(2)$ .

Resume Call 1: $f(3)$ . Substitute return value: $3 imes 2 = 6$ . Return 6. Pop $f(3)$ .

Final output is 6.

FAQ

Run your own problem

Answer form

References: Introduction to Algorithms (CLRS), Chapter 2 · Khan Academy: Computer Science, Recursive Algorithms