Recursion

C Programming Recursion

A function that calls itself is known as recursive function and the process of calling function itself is known as recursion in C programming.

Example of recursion in C programming

Write a C program to find sum of first n natural numbers using recursion. Note: Positive 

integers are known as natural number i.e. 1, 2, 3....n

#include <stdio.h>
int sum(int n);
int main(){
    int num,add;
    printf("Enter a positive integer:\n");
    scanf("%d",&num);
    add=sum(num);
    printf("sum=%d",add);
}
int sum(int n){
    if(n==0)
       return n;
    else
       return n+sum(n-1);    /*self call  to function sum() */
}

Output

Enter a positive integer:
5
15

In, this simple C program, sum() function is invoked from the same function. If n is not equal to 0 then, the function calls itself passing argument 1 less than the previous argument it was called with. Suppose, n is 5 initially. Then, during next function calls, 4 is passed to function and the value of argument decreases by 1 in each recursive call. When, n becomes equal to 0, the value of n is returned which is the sum numbers from 5 to 1.

For better visualization of recursion in this example:

sum(5)
=5+sum(4)
=5+4+sum(3)
=5+4+3+sum(2)
=5+4+3+2+sum(1)
=5+4+3+2+1+sum(0)
=5+4+3+2+1+0
=5+4+3+2+1
=5+4+3+3
=5+4+6
=5+10
=15

Every recursive function must be provided with a way to end the recursion. In this example when, n is equal to 0, there is no recursive call and recursion ends.

Advantages and Disadvantages of Recursion

Recursion is more elegant and requires few variables which make program clean. Recursion can be used to replace complex nesting code by dividing the problem into same problem of its sub-type.

In other hand, it is hard to think the logic of a recursive function. It is also difficult to debug the code containing recursion.

More Examples on Recursive Function

• C program to Calculate Factorial of a Number Using Recursion

  This program takes a positive integer from user and calculates the factorial of that number. Instead of loops to calculate factorial, this program uses recursive function to calculate the factorial of a number.

  Source Code to Calculate Factorial Using Recursion

  
  

  
  /* Source code to find factorial of a number. */
  
  #include<stdio.h>
  int factorial(int n);
  int main()
  {
      int n;
      printf("Enter an positive integer: ");
      scanf("%d",&n);
      printf("Factorial of %d = %ld", n, factorial(n));
      return 0;
  }
  int factorial(int n)
  {
      if(n!=1)
       return n*factorial(n-1);
  }

  Output

  
  

  Enter an positive integer: 6
  Factorial of 6 = 720

• C program to Reverse a Sentence Using Recusrion

  This program takes a sentence from user and reverses that sentence using recursion. This program does not use string to reverse the sentence or store the sentence.

  Source code to reverse a sentence using recursion.

  
  

  
  

  
  /* Example to reverse a sentence entered by user without using strings. */
  
  #include <stdio.h>
  void Reverse();
  int main()
  {
      printf("Enter a sentence: ");
      Reverse();
      return 0;
  }
  void Reverse()
  {
      char c;
      scanf("%c",&c);
      if( c != '\n')
      {
          Reverse();
          printf("%c",c);
      }
  }

  
  

  Output

  
  

  Enter a sentence: margorp emosewa
  awesome program

  
  

  
  

  
  

  Explanation

  
  

  
  

  This program prints "Enter a sentence: " then, Reverse() function is called. This function stores the first letter entered by user and stores in variable c. If that variable is other than '\n' [ enter character] then, again Reverse()function is called. Don't assume this Reverse() function and the Reverse() function before is same although they both have same name. Also, the variables are also different, i.e., c variable in both functions are also different. Then, the second character is stored in variable c of second Reverse function. This process goes on until user enters '\n'. When, user enters '\n', the last function Reverse() function returns to second last Reverse() function and prints the last character. Second last Reverse() function returns to the third last Reverse() function and prints second last character. This process goes on and the final output will be the reversed sentence.