Imagine you’re in a hall of mirrors, where every mirror shows more mirrors, making a never-ending pattern. This is a lot like recursion, a cool idea in computer science where functions can call themselves.
Recursion works like a Russian nesting doll. Each doll has a smaller doll inside, and inside that one is an even smaller one, and so on. Similarly, recursive functions can solve big problems by breaking them into smaller ones, then breaking those into even smaller ones, until they’re easy to solve.
In C programming, recursion is a handy trick. It helps solve tricky problems neatly. Whether it’s figuring out big math puzzles or exploring complicated structures like trees, recursion is like a special tool that makes things easier.
So, let’s dive into recursion together! It’s like a journey into a world where functions can look at themselves and figure out tough problems piece by piece.
WHAT IS RECURSION IN C?
Recursion is a programming technique where a function calls itself in order to solve a problem. Instead of solving the entire problem at once, recursion breaks it down into smaller, simpler instances of the same problem.
Understanding recursion might seem challenging at first. However, the most effective approach to grasp its workings is through hands-on experimentation and practice.
SYNTAX OF RECURSION IN C
return_type function_name(parameters) {
// Base case(s) - the condition where the function stops calling itself
if (base_condition) {
// Return some value or perform some action
}
// Recursive case(s) - where the function calls itself
else {
// Recursive call with modified parameters
function_name(modified_parameters);
}
}Let’s break down each part:
- return_type: This is the type of value that the function will return. It can be int, void, double, char, or any other data type.
- function_name: This is the name of the function. When calling the function recursively, you'll use the same name.
- parameters: These are the inputs to the function. They can be any data type, including integers, characters, arrays, pointers, etc.
- base_condition: This is the condition that determines when the recursion should stop. It's essential to have a base case to prevent infinite recursion.
Here’s a simple example of a recursive function to calculate the factorial of a number:
int factorial(int n) {
// Base case
if (n == 0 || n == 1) {
return 1;
}
// Recursive case
else {
return n * factorial(n - 1);
}
}There are two main sections in recursion in c, there are
1. Base Case:
The base case is the condition in a recursive function that stops the recursion. It’s like the stopping point where the function no longer needs to call itself and can provide a direct answer. Without a base case, the recursive function would keep calling itself indefinitely, leading to a stack overflow error.
In the factorial example above, the base case is when n equals 0 or 1. At this point, the function returns 1 directly without making another recursive call. This is essential because it provides a stopping condition for the recursion.
Using the above example to differentiate Base Case from Recursive Case
int factorial(int n) {
// Base case
if (n == 0 || n == 1) {
return 1; // This is the base case
}2. Recursive Case:
In C, a recursive case occurs when a function calls itself. This is typically done to solve a smaller instance of the same problem as the current function is solving. It’s like breaking down a big problem into smaller, more manageable pieces. Each time the function calls itself, it’s working on a smaller part of the original problem, moving towards a solution step by step.
else {
return n * factorial(n - 1); // Recursive case
}
}Here’s a breakdown:
Base Case:
- The base case is when n equals 0 or 1.
- In the base case, the function returns 1 directly.
- This is the condition where the recursion stops. When the value of n is 0 or 1 , the function doesn't call itself anymore and simply returns 1.
Recursive Case:
- The recursive case is when n is neither 0 nor 1.
- In the recursive case, the function calls itself with the argument n — 1.
- This is the condition where the function continues to call itself recursively until it reaches the base case.
- The result of factorial(n — 1) is multiplied by n and returned. This process continues until the base case is reached.
MORE EXAMPLES ON RECURSION
#include <stdio.h>
// Direct recursion
void countdown(int n) {
if (n == 0) {
printf("Blastoff!\n");
} else {
printf("%d\n", n);
countdown(n - 1);
}
}
int main() {
countdown(5);
return 0;
}Explanation: The countdown function prints numbers from n to 1, then prints "Blastoff!" when n becomes 0. The function calls itself with n — 1 until n reaches 0.
#include <stdio.h>
// Indirect recursion
void functionA(int n);
void functionB(int n);
void functionA(int n) {
if (n > 0) {
printf("%d ", n);
functionB(n - 1);
}
}
void functionB(int n) {
if (n > 1) {
printf("%d ", n);
functionA(n / 2);
}
}
int main() {
functionA(20);
return 0;
}Explanation: functionA calls functionB, and functionB calls functionA. This creates a circular call pattern between the two functions.
#include <stdio.h>
// Tail recursion
int factorial(int n, int result) {
if (n == 0) {
return result;
} else {
return factorial(n - 1, result * n);
}
}
int main() {
printf("Factorial of 5 is %d\n", factorial(5, 1));
return 0;
}Explanation: The function factorial calculates the factorial of a number using tail recursion. The recursive call factorial(n — 1, result * n) is the last operation performed in each call.
#include <stdio.h>
// Non-tail recursion
int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
int main() {
printf("Fibonacci of 5 is %d\n", fibonacci(5));
return 0;
}Explanation: The fibonacci function calculates the nth Fibonacci number using non-tail recursion. After the recursive calls, it sums up the results of the two previous calls.
#include <stdio.h>
// Nested recursion
int ackermann(int m, int n) {
if (m == 0) {
return n + 1;
} else if (n == 0) {
return ackermann(m - 1, 1);
} else {
return ackermann(m - 1, ackermann(m, n - 1));
}
}
int main() {
printf("Ackermann of (2, 3) is %d\n", ackermann(2, 3));
return 0;
}Explanation: The ackermann function computes the ackermann function using nested recursion. It calls itself with the result of another call to ackermann.
Amazing, you have reached the end and have already become more smarter, valuable, and productive just by learning about Recursion in C
The next step is to implement them. Good luck!
Thanks for reading; if you liked my content and want to support me, the best way is to
1. Follow me on medium
2. Connect With Me On X, LinkedIn and Github, where I keep sharing such free amazing content on programming.
