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:
#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:
- Tail recursion
- 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:
#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;
}
Output
8
Prime Course Trailer
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
Login/Signup to comment