# Recursion in C Programming

The process of calling a function by itself is called recursion and the function which calls itself is called recursive function. Recursion is used to solve various mathematical problems by dividing it into smaller problems. This method of solving a problem is called Divide and Conquer.

In programming, it is used to divide complex problem into simpler ones and solving them individually.

## Syntax of Recursive Function

```returntype recursive_func ([argument list])
{
statements;
... ... ...
recursive_func ([actual argument]);
... ... ...
}```

## Flowchart of Recursion Note: In order to prevent infinite recursive call, we need to define proper exit condition in a recursive function.

For example, consider the program below:

### Example #1: C Program to show infinite recursive function

```#include<stdio.h>

int main()
{
printf("Hello world");
main();
return 0;
}```

In this program, we are calling main() from main() which is recursion. But we haven’t defined any condition for the program to exit. Hence this code will print “Hello world” infinitely in the output screen.

## Types of recursion

• Direct Recursion
• Indirect Recursion

### Direct Recursion

A function is said to be direct recursive if it calls itself directly.

Example #2: C Program Function to show direct recursion

```int fibo (int n)
{
if (n==1 || n==2)
return 1;
else
return (fibo(n-1)+fibo(n-2));
}```

In this program, fibo() is a direct recursive function. This is because, inside fibo() function, there is a statement which calls fibo() function again directly.

### Indirect Recursion

A function is said to be indirect recursive if it calls another function and this new function calls the first calling function again.

Example #3: C Program Function to show indirect recursion

```int func1(int n)
{
if (n<=1)
return 1;
else
return func2(n);
}

int func2(int n)
{
return func1(n);
}
```

In this program, func1() calls func2(), which is a new function. But this new function func2() calls the first calling function, func1(), again. This makes the above function an indirect recursive function.

### Example #4: C program to calculate factorial of a number using recursion.

```#include<stdio.h>
int factorial(int n)
{
if(n==0)
return 1;
else
return (factorial(n-1)*n);
}

int main()
{
int num,f;
printf("Enter a number: ");
scanf("%d",&num);
f=factorial(num);
printf("Factorial of %d = %d",num,f);
return 0;
}```

Here, factorial is calculated using recursion. The formula for calculating factorial of a number n is,

`n! = 1*2*...(n-1)*n `

Again, we can see

`(n-1)! = 1*2*...(n-1)`

Hence we can write,

`n! = (n-1)! * n`

We have implemented this recursive relation in our program.

Here,

• The number whose factorial is to be found is stored in the variable n.
• A recursive function factorial(num) calculates the factorial of the number.
• As factorial is (n-1)! * n, factorial function calculates the factorial by recursively multiplying n with factorial of (n-1).
• Finally, when n = 0, it returns 1 because 0! = 1.

Output

```Enter a number: 7
Factorial of 7 = 5040```

### Example #5: C program print first n Fibonacci numbers using recursion.

```#include<stdio.h>

int fibo(int num)
{
if(num==1||num==2)
return 1;
else
return (fibo(num-1)+fibo(num-2));  // recursive call
}

int main()
{
int i,n;
printf("Enter the required term: ");
scanf("%d",&n);
printf("First %d fibonacci numbers aren",n);
for (i=1; i<=n; i++)
printf("%dn",fibo(i));
return 0;
}```

This program uses recursion to generate Fibonacci series. In a Fibonacci series, nth term can be obtained by adding (n-1)th and (n-2)th term. Mathematically,

```tn = tn-1 + tn-2
```

Here,

• The number of fibonacci terms to be generated is taken from the user and stored in variable n.
• A for loop is used to loop through the number to be generated which is sent to the function fibo. This function is used to calculate and return fibonacci series.
• Inside fibo, if the term-number is 1 or 2, it returns 1. This is because, the first two terms of fibonacci series are both 1. The printed values are 1,1.
• Then the next term-number 3 is passed onto fibo function, since it’s not 1 or 2, the next term in the series is calculated by taking fibo(n – 1) + fibo(n – 2), where n = 3. This calculates the last two terms in the fibonacci series. This is equivalent to fibo(2) + fibo(1), which results in 1 + 1 = 2.
• This recursive loop goes on finally printing the series as 1, 1, 2, 3, 5…

Output

```Enter the required term: 7
First 7 fibonacci numbers are
1
1
2
3
5
8
13```