Recursion, its principle with an example

Recursion is a process in which a function calls itself again and again. We use recursion to solve the bigger problem by dividing it into smaller similar sub-problems and then call them recursively.

In other words, we can also explain it as a problem is broken down into smaller subproblems. And a function applies the same algorithm to each subproblem until it reaches a base case. Here the base case is a straightforward and known solution.

Recursive function has two different parts

Base case
Recursive case

Base case

The base case is used to terminate the task of recurring. If a base case is not defined, then the function will recur an infinite number of times.
The base case gives the conditions in which the recursive calls will halt means collapse the recursion when you hit the base case.

Recursive case

In the Recursive case, the problem space is made smaller and smaller dive deeper into the recursion in the recursive case.
Recursive case simplifies a bigger problem into a number of simpler sub-problems and then calls them.

Example of Recursive function

1. Recursive Program to Calculate Factorial

Factorial Example

Factorial of a non-negative integer n, denoted as n!, is the product of all positive integers from 1 to n.

For example:

0! = 1 (by definition)
1! = 1 (only one number in the product)
5! = 5 x 4 x 3 x 2 x 1 = 120

#include<stdio.h>
long long fact(int num) {
  if (num == 0)
    return 1;
  else
    return (num * fact(num - 1));
}
int main() {
  int i, num, factorial = 1;
  printf("Enter a whole number to find Factorial = ");
  scanf("%d", & num);
  printf("Factorial of %d is: %llu", num, fact(num));
  return 0;
}

Output

Enter a whole number to find Factorial = 5
Factorial of 5 is: 120

2. Fibonacci series Example

A Fibonacci series is a series where next term is equal to the sum of the previous two terms.

Tn=T(n−1)+T(n−2)  
 where  Tn, T(n−1)  and  T(n−2)  are  nth  term,  (n−1)th  term and  (n−2)th  terms respectively.
 And in Series first and second terms are 0 and 1 respectively.
 So,  T1=0  and  T2=1

A Recursive method to Calculate the Fibonacci series

int fibonacci(int i){ 
     if(i==0) return 0; 
     else if(i==1) return 1; 
     else return (fibonacci(i-1)+fibonacci(i-2));
 }

To Print the Fibonacci series

printf("fibonacci series is : \n");
     for(i=0;i<n;i++) { 
         printf("%d ",fibonacci(i));
}

Complete Recursive Program to calculate Fibonacci series

#include<stdio.h>
#include<conio.h>
int fibonacci(int);
int main(){ 
	int n, i; 
	printf("Enter the number of element you want in series :"); 
	scanf("%d",&n); 
	printf("fibonacci series is : \n");
	for(i=0;i<n;i++) { 
		printf("%d \n",fibonacci(i));
	}
	getch();
}
int fibonacci(int i){ 
	if(i==0) return 0; 
	else if(i==1) return 1; 
	else return (fibonacci(i-1)+fibonacci(i-2));
}