C Recursion

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function. Using recursive algorithm, certain problems can be solved quite easily.

WAP in C to Calculate the factorial of a number using recursion

#include<stdio.h>
long int fact(int n);
void main()
{
  int n;
  long int x;
  printf("Enter a positive integer: ");
  scanf("%d",&n);
  x=fact(n);
  printf("Factorial of %d = %ld", n, x);
  getch();
}
long int fact(int n)
{
  if (n>=1)
    return n*fact(n-1);
  else
    return 1;
}

Output

Enter a positive integer : 6
Factorial of 6 = 720

WAP in C to GCD of Two Numbers using recursion

#include <stdio.h>
int hcf(int n1, int n2);
void main()
{
  int n1, n2,x;
  printf("Enter two positive integers: ");
  scanf("%d %d", &n1, &n2);
  x= hcf(n1, n2);
  printf("G.C.D of %d and %d is %d.", n1, n2,x);
  getch();
}
int hcf(int n1, int n2)
{
  if (n2 != 0)
    return hcf(n2, n1 % n2);
  else
    return n1;
}

Output

Enter two positive integers: 366
60
G.C.D of 366 and 60 is 6.

WAP in C to print fibbonacci series using recursion

#include<stdio.h>    
void printFibonacci(int n)
{    
    static int n1=0,n2=1,n3;    
    if(n>0){    
         n3 = n1 + n2;    
         n1 = n2;    
         n2 = n3;    
         printf("%d ",n3);    
         printFibonacci(n-1);    
    }    
}    
int main()
{    
    int n;    
    printf("Enter the number of elements: ");    
    scanf("%d",&n);    
    printf("Fibonacci Series: ");    
    printf("%d %d ",0,1);    
    printFibonacci(n-2);//n-2 because 2 numbers are already printed    
  return 0;  
 }    

Output

Enter the number of elements:15
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

Advantages and Disadvantages of Recursion

Advantages:
i. The main benefit of a recursive approach to algorithm design is that it allows programmers to take advantage of the repetitive structure present in many problems.
ii. Complex case analysis and nested loops can be avoided.
iii. Recursion can lead to more readable and efficient algorithm descriptions.
iv. Recursion is also a useful way for defining objects that have a repeated similar structural form.

Disadvantages:
i. Slowing down execution time and storing on the run-time stack more things than required in a non recursive approach are major limitations of recursion.
ii. If recursion is too deep, then there is a danger of running out of space on the stack and ultimately program crashes.
iii. Even if some recursive function repeats the computations for some parameters, the run time can be prohibitively long even for very simple cases.