13.2 Tricks of the Trade: Tracing a Recursive Function

Hand-tracing an algorithm's execution provides us with valuable insight as to how that algorithm works. We can also trace the execution of a recursive procedure or function. We will illustrate how to do this by studying a recursive function next.

In the last section, we wrote the recursive function Multiply (see Program 13.1). We can trace the execution of the function call Multiply(6,3) by drawing an activation frame corresponding to each call of the function. An activation frame shows the parameter values for each call and summarizes its execution.

The three activation frames generated to solve the problem of multiplying 6 by 3 are shown in Figure 13.2. Each downward arrow indicates a recursive call of the function; the arrow is drawn starting from the line of the activation frame in which the recursive call is made. The value returned from each call is shown alongside each upward arrow. The upward arrow from each function call points to the operator + because the addition is performed just after the return.

Figure 13.2
Trace of Function Answer := Multiply(6,3)

Figure 13.2

Figure 13.2 shows that there are three calls to function Multiply. Parameter M has the value 6 for all three calls; parameter N has the values 3, 2, and finally 1. Because N is 1 in the third call, the value of M (i.e., 6) is returned as the result of the third and last call. After returning to the second activation frame, the value of M is added to this result and the sum (i.e., 12) is returned as the result of the second call. After returning to the first activation frame, the value of M is added to this result and the sum (i.e., 18) is returned as the result of the original call to function Multiply.

Parameter and Local Variable Stacks

You may be wondering how Ada keeps track of the values of M, N, and Result at any given point. Ada uses a special data structure, called a stack, that is analogous to a stack of dishes or trays. Think of the countless times you have stood in line in a cafeteria. Recall that clean dishes are always placed on top of a stack of dishes. When we need a dish, we always remove the one most recently placed on the stack. This causes the next to last dish placed on the stack to move to the top of the stack.

Similarly, whenever a new function call occurs, the parameter values associated with that call are placed ("pushed") on the top of the parameter stack. Also, a new cell whose value is initially undefined is placed on top of the stack that is maintained for the local variable Result. Whenever M, N, or Result is referenced, the value at the top of the corresponding stack is always used. When a procedure return occurs, the value currently at the top of each stack is removed ("popped"), and the value just below it moves to the top, just as in the cafeteria stack.

As an example, let's look at the three stacks right after the first call to Multiply (but before Multiply does any work). There is one cell on each stack, as shown below. Result has no value yet, because Multiply computes it.

After first call to Multiply:

 	M	N	Result

	|6|	|3|	|?|

Just after the second call to Multiply, the number 2 is placed on top of the stack for N, and the top of the stack for Result becomes undefined again as shown below. The top cells represent the top of each stack.

After second call to Multiply:

 	M	N	Result

	|6|	|2|	|?|
	|6|	|3|	|?|

Multiply is called again, and this time the number 1 is placed on top of the stack.

After third call to Multiply:

 	M	N	Result

	|6|	|1|	|?|
	|6|	|2|	|?|
	|6|	|3|	|?|

Because 1 is the stopping case, Result can be computed. After first computation of Result:

 	M	N	Result

	|6|	|1|	|6|
	|6|	|2|	|?|
	|6|	|3|	|?|

The function can now return, which causes the values at the top of the stack to be removed. Because Multiply was called in a statement that computes Result, a new value of Result is placed on top of the stack.

After first return and second computation of Result:

	M	N	Result

	|6|	|2|	|12|
	|6|	|3|	|?|

The function can now return yet again and compute a new value of Result.

After second return and third computation of Result:

	M	N	Result

	|6|	|2|	|18|

Finally, we return to the main program; the final value of Result is left on top of the stack, where it can be picked up and copied into Answer.

After third return:

	M	N	Result

	|?|	|?|	|18|

Because these steps are all done automatically by Ada, we can write recursive subprograms without needing to worry about the stacks.

Implementation of Parameter Stacks in Ada

For illustrative purposes, we have used separate stacks for each parameter in our discussion; however, the compiler actually maintains a single stack. Each time a call to a subprogram occurs (even a nonrecursive one), all its parameters and local variables are pushed onto the stack along with the memory address of the calling statement. The latter gives the computer the return point after execution of the procedure or function. Although there may be multiple copies of a procedure's parameters saved on the stack, there is only one copy of the procedure body in memory.

We have introduced the stack here as a way to explain how recursive calls can be implemented. However, stacks are used by most programming languages to implement all subprogram calls, not just recursive ones. Indeed, recursive calls are really just a special case in which the calling and called subprograms are the same.

Exercises for Section 13.2

Self-Check

Trace the execution of Multiply(5,4) and show the stacks after each recursive call.