Recursion

Recursion

A function call is said to be recursive, if we invoke a function from within the same function.  The phenomenon being referred to as recursion.  A termination condition must be specified with each recursive call to avoid infinite execution of that function.  Recursion is basically required whenever a function has to operate upon different set of values to obtain the result.

The recursive calls must store the intermediate results of arguments of arguments and local variables.  Recursive calls cannot store these values in the memory allocated to variables during compile time, hence dynamic memory management issues are involved in recursion.  Thus, the arguments must be stored along with the return address to evaluate the result, since most recently saved variables are restored first.  Thus activation stacks are created which support LIFO (Last In First Out) order for the purpose of evaluating result in recursion.

Thus recursion may also be used in programs that must operate in Last In First Out order.  Recursive programs may also be written using non-recursive approach to programming either with the use of stack or by using GOTO to transfer the control to any specific part of the program, wherever required.  However, some recursive functions may be converted to iterative definitions simply by using an iterative construct.

Recursion is explained further with examples such as computing factorial of a given number, computing GCD (Greatest Common Divisor), solving Towers of Hanoi problem, raising a number to a given power etc.

Recursive function to find the factorial of a given number:

/*Recursive Definition*/

int factorial(int n)
{if(n==0)
return 1;
else
return(n*factorial(n-1));
}

As the above definition implies, computing a factorial using recursion is similar to computing method performed manually.  The recursive function may be converted to non-recursive/iterative function as follows:

/*Non-Recursive Definition*/

int factorial(int n)
{int i,res=1;
for(i=n;i>=1;i–)
res=res*i;
return(res);
}

If we compare the recursive definition with the iterative one, we note that recursion is eliminated by using a for loop for operating n times restoring the value at each call in a variable called res.  Thus, we may write a recursive algorithm considering the basic step required to sort out a given problem.

• Program to compute factorial of a given number:

  Recursion

  Program to compute factorial of a given number

  #include <stdio.h>
  #include <conio.h>

  /*Recursive Definition*/
  /*int factorial(int n)
  {if(n==0)
  return 1;
  else
  return(n*factorial(n-1));
  }
  */
  /*Non-Recursive Definition*/

  int factorial(int n)
  {int i,res=1;
  for(i=n;i>=1;i–)
  res=res*i;
  return(res);
  }

  void main()
  {
  int num,res;
  clrscr();
  printf(“\nEnter number to compute factorial?”);
  scanf(“%d”,&num);
  res=factorial(num);
  printf(“\nFactorial = %d”,res);
  getch();
  }

Recursive function to solve Towers of Hanoi Problem: 

This problem is all about shifting disks from one pillar to the other pillar using a third pillar such that only one disk from the top may be moved at a time such that it is transferred to one pillar while considering that larger disk should be at the bottom of smaller disk.  Recursion is used to solved Towers of Hanoi problem, since it involves repetitive shifting of disks from one pillar to the other.  The ‘C’ recursive function for the same is given below with the output to trace the execution of the program:

void hanoi(int num_disks,char *src,char *tmp,char *trgt)
{
if(num_disks==1)
{printf(“\nMove disk from %s to %s”,src,trgt);
}
else
{
hanoi(num_disks-1,src,trgt,tmp);
printf(“\nMove disk from %s to %s”,src,trgt);
hanoi(num_disks-1,tmp,src,trgt);
}
}

• Program to solve Towers of Hanoi problem:

  Recursion

  Program to solve Towers of Hanoi problem

  #include <stdio.h>
  #include <conio.h>

  void hanoi(int num_disks,char *src,char *tmp,char *trgt);

  void main()
  {
  int disks;
  char source[10],temp[10],target[10];
  clrscr();
  printf(“\nEnter total number of disks?”);
  scanf(“%d”,&disks);
  printf(“\nEnter source pillar?”);
  scanf(“%s”,source);
  printf(“\nEnter intermediate pillar?”);
  scanf(“%s”,temp);
  printf(“\nEnter target pillar?”);
  scanf(“%s”,target);
  hanoi(disks,source,temp,target);
  getch();
  }

  void hanoi(int num_disks,char *src,char *tmp,char *trgt)
  {
  if(num_disks==1)
  {printf(“\nMove disk from %s to %s”,src,trgt);
  }
  else
  {
  hanoi(num_disks-1,src,trgt,tmp);
  printf(“\nMove disk from %s to %s”,src,trgt);
  hanoi(num_disks-1,tmp,src,trgt);
  }
  }

  Output:

  Enter total number of disks?3

  Enter source pillar?First

  Enter intermediate pillar?Second

  Enter target pillar?Third

  Move disk from First to Third
  Move disk from First to Second
  Move disk from Third to Second
  Move disk from First to Third
  Move disk from Second to First
  Move disk from Second to Third
  Move disk from First to Third

Recursive function to compute GCD of a given number:

To compute the greatest common divisor of two given numbers x and y, if x is lesser than y, then GCD is invoked with alternate set of arguments.  If the second argument y=0, the first argument x is returned, otherwise GCD function is called with the arguments as y and xmody.  The ‘C’ function for computing GCD is given below:

/*Recursive function to compute GCD*/

int GCD(int x,int y)
{
if(y==0)
return x;
else if(x<y)
return GCD(y,x);
else
return GCD(y,x%y);
}

• Program to compute GCD of given two numbers x and y:

  Recursion

  Program to compute GCD of given two numbers x and y

  #include <stdio.h>
  #include <conio.h>

  /*Recursive function to compute GCD*/
  int GCD(int x,int y)
  {
  if(y==0)
  return x;
  else if(x<y)
  return GCD(y,x);
  else
  return GCD(y,x%y);
  }

  void main()
  {
  int x,y,res;
  clrscr();
  printf(“\nEnter first number?”);
  scanf(“%d”,&x);
  printf(“\nEnter second number?”);
  scanf(“%d”,&y);
  res=GCD(x,y);
  printf(“\nGCD of %d and %d is %d”,x,y,res);
  getch();
  }

Recursive function to compute power of a given number:

The power of a given number may be computed by using the following function, f(x,n):

f(x,n) =                     1                ;      if n=0

                x * x^n-1   ;      if n>0

/*Recursive definition to computer power of a given number*/

int power(int x,int n)
{
if(n==0)
return 1;
else
return(x * power(x,n-1));
}