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

**Output**

```
Enter the number of element you want in series :5
fibonacci series is :
0
1
1
2
3
```