# 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*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 are\n",n); for (i=1; i<=n; i++) printf("%d\n",fibo(i)); return 0; }

This program uses recursion to generate Fibonacci series. In a Fibonacci series, n^{th} 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

## Disadvantages of Recursion

- Recursive programs are generally slower than non recursive programs because it needs to make a function call so the program must save all its current state and retrieve them again later. This consumes more time making recursive programs slower.
- Recursive programs requires more memory to hold intermediate states in a stack. Non recursive programs don't have any intermediate states, hence they don't require any extra memory.