chap listsstacksand queues ter is maderequiring that the stack store the calling address (say and current value (which is at this pointwe have reached the base case for factand so the recursion begins to unwind each return from fact involves popping the stored value for from the stackalong with the return address from the function call the return value for fact is multiplied by the restored value for nand the result is returned because an activation record must be created and placed onto the stack for each subroutine callmaking subroutine calls is relatively expensive operation while recursion is often used to make implementation easy and clearsometimes you might want to eliminate the overhead imposed by the recursive function calls in some casessuch as the factorial function of section recursion can easily be replaced by iteration example as simple example of replacing recursion with stackconsider the following non-recursive version of the factorial function static long fact(int /compute /to fit nin long variablerequire assert ( > &( < " out of range"/make stack just big enough stack new astack( )while ( push( --)long result while ( length( result result pop()return resultherewe simply push successively smaller values of onto the stack until the base case is reachedthen repeatedly pop off the stored values and multiply them into the result in practicean iterative form of the factorial function would be both simpler and faster than the version shown in example unfortunatelyit is not always possible to replace recursion with iteration recursionor some imitation of itis necessary when implementing algorithms that require multiple branching such as in the towers of hanoi algorithmor when traversing binary tree the mergesort and quicksort algorithms of are also examples in which recursion is required fortunatelyit is always possible to imitate recursion with stack let us now turn to non-recursive version of the towers of hanoi functionwhich cannot be done iteratively