C programming recursion


In this tutorial, you will learn about c programming recursion with the examples of recursive functions.

c programming recursion

C programming recursive functions


Until now, we have used multiple functions that call each other but in some case, it is useful to have functions that call themselves. In C, such function which calls itself is called recursive function and the process is called recursion.

For example:

main ()
{
  printf("Recursion \n");
  main();
}

In this above example, main function is again called from inside the main function. So this function will keep on printing Recursion until the program run out of memory.

Example of recursive function: C program to find the factorial of first 3 natural numbers using recursion

#include <stdio.h>
long int fact( int n )
 { 
     if ( n <= 1 )
        return 1;
     else      //recursive step
        return ( n * fact (n-1) );
 }    //end factorial
int main ()
 {
     int i;
     for ( i = 1; i <=3; i++ )
        printf("%d! = %d\n",i, fact(i) );
     return 0;
}

Output

1! = 1
2! = 2
3! = 6

 

Explanation of output

when i = 1 | fact (1) : 1 * fact(0) = 1*1 = 1
when i = 2 | fact (2) : 2 * fact(1) = 2*1 = 2 
when i = 3 | fact (3) : 3 * fact(2) = 3*2 = 6

Explanation of the program

First of all, the recursive factorial function checks whether if condition is true or not i.e whether n is less than or equal to 1. If condition is true, factorial returns 1 and the program terminates otherwise the following statement executes.

return ( n * fact (n-1) );

c recursion

Common Programming Errors
Forgetting the base case or incorrect recursion step that does not converge will cause infinite recursion.

 

Difference between recursion and iteration


  • Iteration uses a repetition statement whereas recursion does repetition through repeated function calls.
  • Iteration terminates when loop condition fails whereas recursion terminates when the base case became true.