Tracing Recursion

Tracing a recurive program is not much different from tracing a regular program. The most important point is to follow the code exactly and keep track of the current call frame.

Let us track the execution of factorial(3).

1. The first invocation invokes with n equals to 3. The first call frame is constructed with n=3 and the return address is whatever code we need to return to.
2. The conditional statement dictates that we need to compute n * factorial(n-1). This means we need to compute factorial(2).
3. The second call frame is now constructed with a return address to continue the computation of 3 * factorial(2) and n=2.
4. Again, the conditional statement dictates that we need to computer 2 * factorial(1).
5. The third call frame is constructed with a return address to continue the computation of 2 * factorial(1) and n=1.
6. With this third call frame (n=1), the conditional statement executes the else-part and return a value of 1. This means factorial(1) evaluates to 1.
7. The third invocation of factorial returns. The associated call frame is deallocated. The result of 1 is ``plugged into'' 2 * factorial(1) so it becomes 2 * 1.
8. The result of 2 * 1 is returned as the second invocation of factorial concludes. This means the call frame of the second invocation of factorial (with n=2) is now deallocated. We return to the execution of 3 * factorial(2).
9. From the second invocation of factorial we know that factorial(2) is 2, we plug this into 3 * factorial(2) and get an answer of 6.
10. The first invocation of factorial now returns with a result of 6. This value of 6 is ``plugged into'' whatever invoked factorial(6) in the first place.

It helps when one remembers that the allocation and deallocation of call frames follows the LIFO (last-in-first-out) order. The code always refers to the call frame at the ``top'' of the stack.