Recursion in c programming

 

    

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called recursive function.

1.Direct recursion : If a function calls the same function then it is known as direct recursion. 

Example :

 void func( ) 
 {
   //some code..... 
    func( ); 
   //some code.... 
 }
 

2.Indirect recursion : If a function calls a different function it is known as indirect recursion. 

Example :

 void func1( ) 
 {
   //some code..... 
    func2( ); 
   //some code.... 
 }
 void func2( ) 
 {
   //some code..... 
   func1( ); 
   //some code.... 
 }
 

The recursion continues until a particular condition is met to prevent it from entering it into an infinite loop. 

Below is an example of finding the factorial of a given number using recursion. 

A factorial is the product of an integer and all the positive integers less than it. A factorial is denoted by the symbol !

For example, 

$4!4!!$4! (read as four factorial) represents the following:

$$0! = 1

$1! = 1$

$2! = 2 \times 1 = 2$

$3! = 3 \times 2 \times 1 = 6$

$4! = 4 \times 3 \times 2 \times 1 = 24$

Program : 

  #include<stdio.h>
  int factorial(int n) 
  {
     if(n==0||n==1)  //Stop condition
          return 1;
     else
          return n*func(n-1) ;
   }
   int main( ) 
   {  
      int n;
      printf("Enter the number to find it's factorial ") ;                             
      scanf("%d",&n);
      printf("Factorial of %d is : %d",n,factorial(n);
      return 0;
   }
   
   Output :
   
   Enter the number to find it's factorial 4
   Factorial of 4 is : 24
 

Memory Allocation in recursion

When a function is called the memory is allocated for it on a stack, the memory for a called function is allocated on top of the memory allocated to calling function and a different copy of local variables is created for each function call. 

When the base(stop) condition is reached the function returns it's value to the function by whom it is called and memory is de-allocated and the process continues. 

Below is an illustration of Memory Stack

For the above factorial program using recursion the stack content will be 

As we can see above the factorial(1) returns 1 to factorial (2) and factorial(2) returns 2*1 to factorial(3) and factorial (3) returns 6(3*2*1) to factorial(4) Returns 24(4*3*2*1).