Lists, Stacks, and Queues - Data Structures and Algorithm Analysis - page 122

β

Currptr

3

n 2

β

β

Currptr Currptr

2 2

n 3 n 3

β

β 1 β

Currptr Currptr

Currptr

1 1

n 4 n 4 n 4

β β β β

Currptr Currptr Currptr Currptr

Call fact(4) Call fact(3) Call fact(2) Call fact(1)

β

Currptr

2

n 3 Return 24

β β

Currptr Currptr

1 1

n 4 n 4

β β β

Currptr Currptr Currptr

Return 1 Return 2 Return 6

Figure4.22 Implementing recursion with a stack. values indicate the address
of the program instruction to return to after completing the current function call.
On each recursive function call to fact (as implemented in Section 2.5), both the
return address and the current value of n must be saved. Each return from fact
pops the top activation record off the stack.

current value for n (which is 4), is saved on the stack. Function fact is invoked
with input parameter 3.
In similar manner, another recursive call is made with input parameter 2, re-
quiring that the address from which the call is made (say 2 ) and the current value
for n (which is 3) are stored on the stack. A final recursive call with input parame-
ter 1 is made, requiring that the stack store the calling address (say 3 ) and current
value (which is 2).
At this point, we have reached the base case for fact , and so the recursion
begins to unwind. Each return from fact involves popping the stored value for
n from the stack, along with the return address from the function call. The return
value for fact is multiplied by the restored value for n, and the result is returned.
Because an activation record must be created and placed onto the stack for
each subroutine call, making subroutine calls is a relatively expensive operation.
While recursion is often used to make implementation easy and clear, sometimes