Recursion in C Programming
Hello Everyone, In this article, we will cover the concept of Recursion in C Programming. We will cover the basics of recursion, understand how it works, and see some examples to help you grasp this concept easily. Whether you’re new to C or have some experience, this guide will help you to understand Recursion in C effectively. Let’s get started.
Recursion is a programming concept where a function calls itself in order to solve a problem. It is particularly useful for breaking down complex problems into smaller, more manageable sub-problems. In C programming, recursion is implemented by creating a function that calls itself directly or indirectly.
C Program to calculates the factorial of a given number (n!)
#include <stdio.h>// Recursive function to calculate the factorial of a given number
unsigned long long factorial(int n) {
if (n == 0) { // Base case: 0! = 1
return 1;
} else { // Recursive case: n! = n * (n-1)!
return n * factorial(n - 1);
}
}
int main() {
int number;
printf("Enter a positive integer: ");
scanf("%d", &number);
if (number < 0) {
printf("Factorial is not defined for negative numbers.\\n");
} else {
unsigned long long result = factorial(number);
printf("Factorial of %d is %llu\\n", number, result);
}
return 0;
}
In this example, the factorial function calculates the factorial of a given number n. If n is 0, the function returns 1 (the base case). Otherwise, the function calls itself with the argument n – 1 and multiplies the result by n (the recursive case). The recursion stops when it reaches the base case (n == 0).
The main function handles user input and calls the factorial function to compute the result. It then prints the result to the console.
Example 1: Fibonacci Sequence C Program
This example demonstrates a recursive function in C programming that calculates the nth Fibonacci number. In the Fibonacci sequence, each number is the sum of the two preceding ones, starting from 0 and 1.
#include <stdio.h>// Recursive function to calculate the nth Fibonacci number
int fibonacci(int n) {
if (n == 0) {
return 0; // Base case 1: F(0) = 0
} else if (n == 1) {
return 1; // Base case 2: F(1) = 1
} else {
return fibonacci(n - 1) + fibonacci(n - 2); // Recursive case: F(n) = F(n-1) + F(n-2)
}
}
int main() {
int number;
printf("Enter a positive integer: ");
scanf("%d", &number);
if (number < 0) {
printf("Fibonacci numbers are not defined for negative numbers.\\n");
} else {
int result = fibonacci(number);
printf("Fibonacci number F(%d) is %d\\n", number, result);
}
return 0;
}
Output:
Enter a positive integer: 10
Fibonacci number F(10) is 55
Example 2: Sum of Natural Numbers
This example demonstrates a recursive function in C programming that calculates the sum of natural numbers from 1 to n.
#include <stdio.h>// Recursive function to calculate the sum of natural numbers from 1 to n
int sumOfNaturalNumbers(int n) {
if (n == 1) {
return 1; // Base case: sum(1) = 1
} else {
return n + sumOfNaturalNumbers(n - 1); // Recursive case: sum(n) = n + sum(n-1)
}
}
int main() {
int number;
printf("Enter a positive integer: ");
scanf("%d", &number);
if (number < 1) {
printf("Please enter a positive integer.\\n");
} else {
int result = sumOfNaturalNumbers(number);
printf("Sum of natural numbers from 1 to %d is %d\\n", number, result);
}
return 0;
}
Output:
Enter a positive integer: 5
Sum of natural numbers from 1 to 5 is 15