What is the purpose of a stack in implementing a recursive procedure Explain?

Answer 1

there is no a prior limit on the depth of nested recursive calls (that a recursive function may call itself any no. of times), we may need to save an arbitrary number of register values(return values of the recursive functions, that may be used latter to find the actual solution). These values must be restored in the reverse of the order in which they were saved, since in a nest of recursions the last subproblem to be entered is the first to be finished. This dictates the use of a stack, or ``last in, first out'' data structure, to save register values. We can extend the register-machine language to include a stack by adding two kinds of instructions: Values are placed on the stack using a save instruction and restored from the stack using a restore instruction. After a sequence of values has been saved on the stack, a sequence of restores will retrieve these values in reverse order.

Vishal Srivastava

MCA, LU

source : http://mitpress.mit.edu/sicp/full-text/sicp/book/node110.html

Answer 2

A recursive approach to a problem solution involves doing something, and then setting the results aside for a moment while you go do that same something again with different parameters in a nested fashion. That nested call may yet make another nested call, setting aside its results, and on and on...

Ultimately, one of the nested calls returns. When that happens, you want to go back to where you were before you made that last nested call, and pick up the calculation where you left off, finish it, and return. This process repeats, effectively unwinding the nesting sequence in the reverse order in which it was made.

A stack is a perfect vehicle to accomplish this with, because the order in which things get popped off of the stack is the reverse order in which they were originally pushed on. Typically, the stack contains saved registers, local variables, and formal parameters, all intermingled in the order in which they were saved, all returned in the reverse order.

Answer 3

A stack is a data structure that contains information that is retrieved in the reverse order of it being stored. In other words, it is a LIFO - Last In First Out, type of structure. The stack is perfectly suited for recursive functions because the stack can store the function parameters and local variables, LIFO, as the recursion depth increases. This "saves" the state of the function at the point of recursion, and then unwinds the stack when the function finally does return.

The classic example of a recursive function is the factorial function...

int nfact (n) if (n < 2) return n; else return n * nfact (n - 1);

...if you analyze the stack, you will see that it contains alternating copies of partial products along with decrementing N's, until N reaches 1, at which point everything unwinds.

Answer 4

The role of the call stack is the same regardless of whether a function call is recursive or not. The call stack is used to store the return address of the calling function. It is also used to provide storage for the function's local variables including its formal arguments.

Return addresses remain on the call stack until a function ends or returns, at which point the return address is popped from the stack and control is returned to that address. In this way, functions can call other functions (including themselves) without ever losing track of where those calls originated.

Using the call stack to store formal arguments and local variables is faster than allocating memory from the heap because the call stack is already allocated. Each thread has its own call stack which is allocated when the thread is instantiated and is released when the thread terminates. A call stack pointer keeps track of the top of the call stack (the next unused address), thus pushing and popping values to and from the call stack has minimal runtime cost. However, the call stack is fixed size (determined at compile time) and the caller cannot reference call stack memory utilised by the callee upon return from the callee because that memory is no longer in scope and may change at any time. Hence we use the heap to maintain large data structures as well as to allow the caller and callee to share memory.