21. Recursion in C

 

Recursion in C

Recursion is a 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 number of recursive calls. Recursion cannot be applied to all the problems, but it is more useful for the tasks that can be defined in terms of similar subtasks. Any problem that can be solved recursively can also be solved iteratively.

#include <stdio.h>

int fact(int);
int main()
{
   int n, f;
   printf("Enter the number whose factorial you want to calculate : ");
   scanf("%d", &n);
   f = fact(n);
   printf("Factorial of %d = %d", n, f);
   return 0;
}
int fact(int n){
   if (n == 0){
      return 0;
   }
   else if (n == 1){
      return 1;
   }
   else {
      return n*fact(n-1);
   }
}

Output :

Enter the number whose factorial you want to calculate : 5
Factorial of 5 = 120

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, 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.

#include <stdio.h>

int fibonacci(int);
void main()
{
   nt n, f;
   printf("Enter the value of n : ");
   scanf("%d", &n);
   f = fibonacci(n);
   printf("%d term of the fibonacci series is %d.", n, f);
}
int fibonacci(int n){
   if (n == 0 || n == 1){
      return 1;
   }
   else{
      return fibonacci(n-1) + fibonacci(n-2);
   }
}

Output :

Enter the value of n : 0
0 term of the fibonacci series is 0.
Enter the value of n : 10
10 term of the fibonacci series is 55.

Memory Allocation of Recursive Method

Each recursive call creates a new copy of that memory in the memory. Once some data is returned by the method, the copy is removed from the memory. Since the variables and the other stuff declared inside the function gets stored in the stack, therefore a separate stack is maintained at each recursive call. Once the value is returned from the corresponding function, the stack gets destroyed.