11.2 – Recursion – Memory, Stack overflow

by subbu on December 8, 2013

Recursion – Memory:

As we have discoursed in the previous session Memory – Stack segment, parameters and local variables are placed on the stack (push) on calling a function. These variables are taken off (pop) on termination of function execution.

While calling a function itself (winding), different versions of variables are placed on the stack. While unwinding recursion these versions are taken off one by one.

Now we will see what happens when we send 3 to the following recursive function to find the sum of 1 to 3 natural numbers (1+2+3)

int sum(int n)
{
 int sm;
 if(n==1)  /* terminating condition */
   return 1;
 sm=n+sum(n-1);
 return sm;
}

Forwarding recursion (Winding):

While forwarding recursion, arguments, local variables and a place holder to store return value are pushes on to the stack. There would be a separate stack frame for every iteration.

Now we will see what happens in the stack segment step by step

s=sum(3);

On calling the function sum() by sending 3 as argument, a stack frame with parameter n(3), local variable sm and a place holder to store return value is created. Control starts executing the function once the stack frame is created

Recursion winding-1

As the condition “3==1” is false,

sm=3+sum(2);

is executed. On calling function sum() recursively by sending 2 as argument, a stack frame with parameter n(2), local variable sm and a place holder to store return value is created. Control starts executing the function for the second time once the stack frame is created

Recursion winding-2

As the condition “2==1” is false,

sm=2+sum(1);

is executed. On calling function sum() recursively by sending 1 as argument, a stack frame with parameter n(1), local variable sm and a place holder to store return value is created. Control starts executing the function for the third time once the stack frame is created.

Recursion winding-3

Unwinding recursion:

As the condition “1==1” is true then the function returns “1” and pop the last stack frame. The returned value is assigned to the place holder of second stack frame, which was created to store returned value.

Recursion unwinding-1

The returned value “1” is added with n(2) and assigns to sm.

recursion unwinding-2

The value of sm is returned and pop the second stack frame. The returned value is assigned to the place holder of first stack frame, which was created to store returned value.

Recursion unwinding-3

Now the returned value “3” is added with n(3) and assigned to sm.

Recursion unwinding-4

Now the value of sm is send to the caller and assigns to s.

Once the execution of recursive function is completed the first stack frame is popped from the stack segment.

Completing recursion

Stack overflow:

As we have discoursed so far, a stack frame with parameters, local variables and a place holder to store returned value is created every time a function calls itself. If there is no termination statement in the recursive function then stack frames will never be popped and there would be a point where there would be no space in the stack segment, results stack overflows, and program will crash or terminate

#include<stdio.h>
void display(int);
int main()
{
 display(10);
 return 0;
}
void display(int n)
{
 printf("%5d",n);
 display(n-1);
}

As there is no termination statement in the recursive function, it leads to stack overflow and depends on the system the program would be crashed at one point.

Why recursion?

Though problems solved by iteration statements can be solved using recursion, it is discouraged of using recursion due to its disadvantages. Some of the disadvantages with recursion are

  • Low performance because takes time to call a function
  • Required more memory because a stack frame is created every time a function is called recursively
  • Relatively difficult to write and debug the code

We can always solve a recursive problem iteratively. However for non-trivial problems, the recursive version is always simple to write and read. We are going to see some of the non-trivial problems in coming sessions.

Previous post:

Next post: