Recursion

Let us discuss one of the widely used method of solving certain class of complex problems.Popularly known as “Recursion”.

What is Recursion?

Recursion is nothing but a function calling itself.The basic idea of recursion is breaking a complex problem into pieces and solving those individual problems and combining the result. We use recursion when there are some set of statements that are to be executed many times.

Basic Idea of Recursion

main ()
{
functionA();
}
functionA();
{
-----statements----;
functionA();
}

There are certain points that are necessarily important in designing a recursive algorithm.

Base condition:

It is an instance of a problem,the solution of which requires no further recursive calls is known as base case. Usually this condition exists in if statement.

Recursive formula:

Every Recursive function contains recurrence formula.This recurrence formula enables us to perform some task many times.

Example Program

int main()
{
int n=5,res;
res=factorial(n);
printf("%d",res);
return 0;
}
int factorial(int n)
{
  if(n==1||n==0)
  return 1;
  else
  return n*factorial(n-1);
}

Iterations:

5*factorial(4)

5*4*factorial(3)

5*4*3*factorial(2)

5*4*3*2*factorial(1)

5*4*3*2*1

Output:120

Common errors in implementing Recursion:

There are certain errors known as stack overflow and segmentation fault usually occur due to improper base condition.

Example:

void main()
{
functionA();
}
functionA()
{
 static int c=5;
 if(c>0)  // Improper base condition 
 { 
  printf(“%d”,c);
  c++;
  return functionA();
 }
 else
 return 0;
}

Here,we initialized c to 5 and started incrementing it.In the base condition holds true for every iteration. So,the algorithm never terminate and results in run time error.

How Recursion algorithm work:

Generally, the memory for data of any function is allocated in the stack.Therefore,every function that calls any other function or calls itself,places the data on the top of stack.In case of Recursion for each recursive function call,an extra space is allocated in the stack. The data on the top of the stack is utilized by the current executing function call.

Can we call main recursively?

It is perfectly legal to call main recursively provided,there exists a proper base condition.

Consider the following examples:

Proper Implementation

main()
{
 static int c=5;
 if(c-- >0)
 {
  printf(“%d”,c);
  return main();
 }
  else
  return 0;
}

Output:

4 3 2 1 

Improper implementation:

main()
{
 main();
 return 0;
}

Here there is no base condition, so the program execute till a point where run time error occurs due to stack overflow.

Can we initialize variables inside a recursive function?

We must be careful while initializing variables inside a recursive algorithm.This is because for every recursive call, an extra space is allocated in the stack.
Lets consider the general initialization scenario in case of recursion

 main()
{
 functionA();
}

functionA()
{
 int c=5;
 if(c-- )
 {
  printf(“%d”,c);
  return functionA();
 }
  else
  return 0;
}

Output:

Segmentation fault

Proper Initialization of variables inside recursive block

void main()
{
 functionA();
}
functionA()
{
 static int c=5;
 if(c-- )
 {
  printf(“%d”,c);
  return functionA();
 }
  else
  return 0;
}

Output:

4 3 2 1 0

Rule of Thumb

Always initialize variables inside recursive block using static keyword.