# Recursion in C

## Recursion in C Programming

In this page, we have explained all about recursion in C program which includes the different types of recursion in C. ## What is Recursion in C?

Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. A recursive function is a function that calls itself with a smaller input until it reaches a base case, at which point it returns a result.

Example of a recursive function in C that calculates the factorial of a given number:

Run
```#include <stdio.h>

int factorial(int n) {
if (n == 0) {
return 1;
}
return n * factorial(n - 1);
}

int main() {
int num = 5;
printf("The factorial of %d is %d\n", num, factorial(num));
return 0;
}```

### Output

`Factorial of 5 is 120.`

## Types of Recursion

There are two main types of recursion in C:

1. Tail recursion
2. Non-tail recursion

#### Tail Recursion

• This is a type of recursion where the recursive call is the last thing the function does before returning a value.
• Tail-recursive functions are generally preferred over non-tail-recursive functions because they can be optimized by the compiler.
```int factorial(int n) {
if (n == 0) {
return 1;
}
return n * factorial(n - 1);
}
```

#### Non Tail Recursion

• This is a type of recursion where the recursive call is not the last thing the function does before returning a value.
• Non-tail-recursive functions are generally less efficient than tail-recursive functions because they cannot be optimized by the compiler.
```int factorial(int n) {
if (n == 0) {
return 1;
}
int result = factorial(n - 1);
return n * result;
}```

#### Program to calculate the nth number in the Fibonacci sequence using Recursion:

Run
```#include<stdio.h>
int fibonacci(int n) {
if (n == 0 || n == 1) {
return n;
}
else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
int main() {
printf("%d\n", fibonacci(6));  // Output: 8
return 0;
}
```

`8`

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

## Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others