Explain recursion as an application of stack with examples
1 Answer
  1. "Recursion" is technique of solving any problem by calling same function again and again until some breaking (base) condition where recursion stops and it starts calculating the solution from there on. For eg. calculating factorial of a given number
  2. Thus in recursion last function called needs to be completed first.
  3. Now Stack is a LIFO data structure i.e. ( Last In First Out) and hence it is used to implement recursion.
  4. The High level Programming languages, such as Pascal , C etc. that provides support for recursion use stack for book keeping.
  5. In each recursive call, there is need to save the
    1. current values of parameters,
    2. local variables and
    3. the return address (the address where the control has to return from the call).
  6. Also, as a function calls to another function, first its arguments, then the return address and finally space for local variables is pushed onto the stack.

    enter image description here

  7. Recursion is extremely useful and extensively used because many problems are elegantly specified or solved in a recursive way.

  8. The example of recursion as an application of stack is keeping books inside the drawer and the removing each book recursively.
Please log in to add an answer.