The stack is the most convenient data abstraction to use for the bookkeeping recursion entails. To illustrate the translation, and the possibility of enhancing efficiency, the recursive functions towers and next will now be translated into nonrecursive functions.
In towers there are two recursive calls. The idea in implementing it is to write a nonrecursive program that executes just as the recursive program would, while managing the additional records generated by the recursion. This amounts to implementing the procedure described for simulating towers. Each recursive call will be replaced by code to insert the proper return indicator onto a stack, as well as the current scratchpad values. Whenever the end of a recursive call is reached, the proper return indicator and the scratchpad values last put on the stack will be removed and restored to the program's local storage. The earlier recursive version and its implementation as a nonrecursive function are as follows .
Recursive Version
Nonrecursive Version
S_tack is a routine that inserts its arguments, as fields of a record, onto the stack. The name s_tack is used to be sure the compiler can distinguish this routine from the type name stack that also appears in the function. Setstack ensures that the stack will initially contain zero entries; empty returns true if the stack contains no records and false otherwise. The setvar routines do the proper setting of the current scratchpad values for the ensuing recursive call. Restore(&retrn,&n,&i,&a,&f,&s) restores the proper scratchpad values when a return is to be made after completion of some recursive call.
Setvar1(&n,&i,&a,&f) sets n to n - 1 and interchanges the values of f and a.
Setvar2(&n,&i,&a,&f) sets n to n - 1 and interchanges the values of a and i.
The "implicit" exit of the recursive program (after the second recursive call) has been replaced in the implementation by a complex "explicit" sequence of statements. This is because the exit must, in effect, transfer control to the proper place in the calling program. If the stack itself is empty at this point, this means that it is the initial call to towers that has been completed. Return should then be to the calling program. Otherwise, it is some recursive call to towers that has been completed. At this point, the top stack record contains the four scratchpad values to be restored and the return location in towers.
You should simulate the execution of this implementation to see that it really works correctly. The statement labeled "one" corresponds to the first executable statement of the recursive program; this is the statement that is invoked in the implementation to represent a recursive call. It is only invoked, however, after the scratchpad values of the current call and proper return location have been saved on the stack, and the scratchpad values for the upcoming recursive call have been correctly set.
Notice that the implementation requires a stack that can hold the stored information for up to n - 1 recursive calls. The stack must be initialized to empty. Its contents must be preserved between calls. We will not dwell on its implementation details here, but a complete program to test this version is given in Section 4.5.1.
This example highlights the fact that considerable overhead is involved in executing recursive programs. Time is consumed because variables must be stacked and unstacked for each recursive call and its return. It is often possible to discover a more efficient nonrecursive algorithm for a problem, even though the recursive algorithm is evident, as was done in Counting Squares. Nonetheless, the recursive version is frequently clearer, easier to understand, and more concise, as well as easier to verify. Therefore some programmers prefer recursive solutions to problems, even if they are less efficient than the nonrecursive versions.
Another approach is to attempt to increase the efficiency of the iterative program (the implementation) that is translated from a recursive program. This attempt can be made whether or not there is a competing nonrecursive routine.
How can we create a more efficient version of a translated program such as towers? The reason for the stack in the first place is to save return codes and to save scratchpad values that are needed when the suspended call is ready to resume (after the saved values have been unstacked and restored, and the proper program segment is to be executed). If the programmer can determine where the return should be, or what the scratchpad values that are to be restored should be, then this information does not have to be stacked. It may not be necessary to save the values of some other variables. It may also be possible to eliminate some return codes. If no variables need to be saved, and there is only one return code, then the stack itself is not needed. Let us attempt to reach this goal for the implementation of the recursive towers routine.
Notice that in the case statement for retrn at 1, the call to s_tack(2,n,i,a,f,&s) saves the values of the current variables in the suspended call, in order to make the recursive call to towers(n-1,a,i,f). When this new recursive call is completed, these current values will be restored, and the retrn will be 2. The statement labeled "two" will then be executed.
If the stack is empty, the initial call is complete. Otherwise restore will be called immediately and control transferred to the new value of retrn. The current values saved by s_tack(2,n,i,a,f,&s) will never be used, and so need not be saved at all. Thus the call to s_tack( 2,n,i,a,f,&s ) may be eliminated from the program. This means that the only return code appearing will be l in the call to s_tack(1,n,i,a,f,&s). However, the value of retrn after restore is called will always be 1. Therefore, no return code needs to be stored on the stack; the case structure may be removed. Retrn is not needed at all. This new program then looks like the following.
Second Nonrecursive Version
Another improvement can be made by changing the if-else structure to a while loop. Doing so improves the clarity and eliminates the goto:
This yields
Third Nonrecursive Version
5 while loop replaces if-else construct
Finally, the function can be written in more structured form, as follows:
Final Nonrecursive Version
This structured version is more efficient than the compilerlike direct translation because the number of stack operations has been reduced. It is also structured for clarity in reading. Both changes make it a better implementation.
towers(n,i,a,f)
/* Moves the top n disks
from peg i to peg f
*/
int n,i,a,f;
{if(n == 1)
printf("\n %d -> %d\n",i,f);else
{towers(n-1,i,f,a);
printf("\n %d -> %d\n",i,f)towers(n-1,a,i,f);
}
}
towers(n,i,a,f)
/* Moves the top n disks
from peg i to peg f
*/
int n,i,a,f;
{int retrn;
stack s;
setstack(&s);
one: if(n == 1)
printf("\n %d -> %d\n",i,f);else
{s_tack(1,n,i,a,f &s);
setvar1(&n,&i,&a,&f);
goto one;
}
two: if(!empty(&s))
{restore(&retrn,&n,&i,&a,&f,&s);
switch(retrn)
{case 1:
printf("\n %d -> %d\n",i,f)
s_tack(2,n,i,a,f,&s);
setvar2(&n,&i,&a,&f);
goto one;
case 2:
goto two;
}
}
}
towers(n,i,a,f)
/* Moves the top n disks
from peg i to peg f
*/
int n,i,a,f;
{stack s;
setstack(&s);
one: if(n == 1)
printf("\n %d -> %d\n",i,f);else
{s_tack(n,i,a,f,&s);
setvar1(&n,&i,&a,&f);
goto one;
}
if(!empty(&s))
{restore(&n,&i,&a,&f,&s);
printf("\n %d -> %d\n",i,f);setvar2(&n,&i,&a,&f);
goto one;
}
}
one: if(n == 1) one: while(n > 1)
printf("\n %d -> %d\n",i,f); {else s_tack(n,i,a,f,&s);
{ setvar1(&n,&i,&a,&f);s_tack(n,i,a,f,&s); }
setvar1(&n,&i,&a,&f); printf("\n %d -> %d\n",i,f);goto one;
}
towers(n,i,a,f)
/* Moves the top n disks
from peg i to peg f
*/
int n,i,a,f;
{stack s;
one: while(n > 1)
{s_tack(n,i,a,f,&s);
setvar1(&n,&i,&a,&f);
}
printf("\n %d -> %d\n",i,f);if(!empty(&s))
{restore(&n,&i,&a,&f,&s);
printf("\n %d -> %d\n",i,f);setvar2(&n,&i,&a,&f);
goto one;
}
}
towers(n,i,a,f)
/* Moves the top n disks
from peg i to peg f
*/
int n,i,a,f;
{stack s;
int done
done = FALSE;
while(!done)
{while(n > 1)
{s_tack(n,i,a,f,&s);
setvar1(&n,&i,&a,&f);
}
printf("\n %d -> %d\n",i,f);if(!empty(&s))
{restore(&n,&i,&a,&f,&s);
printf("\n %d -> %d\n",i,f);setvar2(&n,&i,&a,&f);
}
else
done = TRUE;
}