**Recursion**

A function defined in C can call itself. This is called recursion.

A function calling itself is also called a recursive function.

**Example of Recursion:**

A very good example of recursion is factorial

```
factorial(n) = 1x 2 x 3...........x n
factorial(n)= 1 x 2 x 3...........n-1 x n
factorial(n)= factorial of (n-1) x n
```

Since we can write factorial of a number in terms of itself, we can program it using recursion.

```
// Function to calculate factorial using recursion
int factorial(int x){
int f;
if(x==0||x==1)
return 1;
else
f=x * factorial(x-1);
return f;
}
```

## What is Recursion in C?

Recursion can be defined as the technique of replicating or doing again an activity in a self-similar way calling itself again and again, and the process continues till specific condition reaches. In the world of programming, when your program lets you call that specific function from inside that function, then this concept of calling the function from itself can be termed as recursion, and the function in which makes this possible is called recursive function.

Here’s an example of how recursion works in a program:Example Syntax:

```
void rec_prog(void) {
rec_prog(); //function calls itself
}
int main(void) {
rec_prog();
return 0;
}
```

C program allows you to do such calling of function within another function, i.e., recursion. But when you implement this recursion concept, you have to be cautious in defining an exit or terminating condition from this recursive function, or else it will continue to an infinite loop, so make sure that the condition is set within your program.

### Factorial Program in C Using Recursion

Example:

```
#include<stdio.h>
#include<conio.h>
int fact(int f) {
if (f==0 || f==1) {
printf("Calculated Factorial");
return 1;
}
return f * fact(f - 1);
}
int main(void) {
int f = 12;
printf("The factorial of %d is %d \n", f, fact(f));
getch();
return 0;
}
```

Output:

Calculated Factorial The factorial of 12 is 479001600

### Fibonacci Program in C Using Recursion

Example:

```
#include<stdio.h>
#include<conio.h>
int fibo(int g) {
if (g == 0) {
return 0;
}
if (g == 1) {
return 1;
}
return fibo(g - 1) + fibo(g - 2);
}
int main(void) {
int g;
printf("Calculated Fibonacci\n");
for (g = 0; g < 10; g++) {
printf("%d \t ", fibo(g));
}
getch();
return 0;
}
```

Output:

Calculated Fibonacci 0 1 1 2 3 5 8 13 21 34

**Important Notes:**

1. Recursion is sometimes the most direct way to code an algorithm

2. The condition which doesn’t call the function any further in a recursive function is called the base condition.

3. Sometimes, due to a mistake made by the programmer, a recursive function can keep running without returning, resulting in a memory error.

#### Practice Question

- Write a program using functions to find the average of three numbers.
- Write a function to convert Celcius temperature into Fahrenheit.
- Write a function to calculate the force of attraction on a body of mass m exerted by earth. (g=9.8m/S
^{2}) - Write a program using recursion to calculate the n
^{th }element of the Fibonacci series. - What will the following line produce in a C program: printf(“%d %d %d\n”,a,++a,a++);
- Write a recursive function to calculate the sum of first n natural numbers.
- Write a program using functions to print the following pattern(first n lines):

```
*
***
*****
```