Recursion in C

Recursion is the process which comes into existence when a function calls a copy of itself to work on a smaller problem. Any function which calls itself is called recursive function, and such function calls are called recursive calls. Recursion involves several numbers of recursive calls. However, it is important to impose a termination condition of recursion. Recursion code is shorter than iterative code however it is difficult to understand.

Recursion cannot be applied to all the problem, but it is more useful for the tasks that can be defined in terms of similar subtasks. For Example, recursion may be applied to sorting, searching, and traversal problems.

  1. #include <stdio.h>  
  2. int fact (int);  
  3. int main()  
  4. {  
  5.     int n,f;  
  6.     printf("Enter the number whose factorial you want to calculate?");  
  7.     scanf("%d",&n);  
  8.     f = fact(n);  
  9.     printf("factorial = %d",f);  
  10. }  
  11. int fact(int n)  
  12. {  
  13.     if (n==0)  
  14.     {  
  15.         return 0;  
  16.     }  
  17.     else if ( n == 1)  
  18.     {  
  19.         return 1;  
  20.     }  
  21.     else   
  22.     {  
  23.         return n*fact(n-1);  
  24.     }  
  25. }  

Output

Enter the number whose factorial you want to calculate?5
factorial = 120

We can understand the above program of the recursive method call by the figure given below:

Recursive Function

A recursive function performs the tasks by dividing it into the subtasks. There is a termination condition defined in the function which is satisfied by some specific subtask. After this, the recursion stops and the final result is returned from the function.

The case at which the function doesn't recur is called the base case whereas the instances where the function keeps calling itself to perform a subtask, is called the recursive case. All the recursive functions can be written using this format.

Pseudocode for writing any recursive function is given below.

  1. if (test_for_base)  
  2. {  
  3.     return some_value;  
  4. }  
  5. else if (test_for_another_base)  
  6. {  
  7.     return some_another_value;  
  8. }  
  9. else  
  10. {  
  11.     // Statements;  
  12.     recursive call;  
  13. }  

Example of recursion in C

Let's see an example to find the nth term of the Fibonacci series.

  1. #include<stdio.h>  
  2. int fibonacci(int);  
  3. void main ()  
  4. {  
  5.     int n,f;  
  6.     printf("Enter the value of n?");  
  7.     scanf("%d",&n);  
  8.     f = fibonacci(n);  
  9.     printf("%d",f);  
  10. }  
  11. int fibonacci (int n)  
  12. {  
  13.     if (n==0)  
  14.     {  
  15.     return 0;  
  16.     }  
  17.     else if (n == 1)  
  18.     {  
  19.         return 1;   
  20.     }  
  21.     else  
  22.     {  
  23.         return fibonacci(n-1)+fibonacci(n-2);  
  24.     }  
  25. }  

Output

Enter the value of n?12 
144