C programming recursion

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

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) );

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.