C Recursion
What is Recursion in C?
Recursion in C is a programming technique in which a function calls itself to solve a problem.
A recursive function repeatedly executes until a specified stopping condition, known as the base case, is reached.
Recursion is commonly used to solve problems such as factorial calculation, Fibonacci series, tree traversal, and divide-and-conquer algorithms.
Example
int factorial(int n)
{
if(n == 1)
return 1;
return n * factorial(n – 1);
}
Explanation
• factorial() is a recursive function.
• The function calls itself using factorial(n – 1).
• The base case is n == 1.
• Recursion stops when the base case is reached.
• Each recursive call returns a value to the previous call.
Why is Recursion Important?
Recursion is important because it:
• Solves complex problems using smaller subproblems.
• Makes code shorter and easier to understand.
• Is useful for tree and graph algorithms.
• Supports divide-and-conquer techniques.
• Is widely used in mathematical and algorithmic problems.
Types of Recursion in C
Recursion can be classified into different types based on how recursive functions call themselves.
The most common types of recursion are:
• Direct Recursion
• Indirect Recursion
• Tail Recursion
Each type is used in different programming situations.
Direct Recursion
Direct recursion occurs when a function calls itself directly within its own definition.
It is the most common type of recursion used in C programming.
Example
void display(int n)
{
if(n == 0)
return;
printf(“%d “, n);
display(n – 1);
}
Explanation
• display() directly calls itself.
• The recursion continues until n becomes 0.
• The base case stops further recursive calls.
• Direct recursion is simple and easy to understand.
Indirect Recursion
Indirect recursion occurs when one function calls another function, and that function eventually calls the first function.
This creates a recursive cycle involving multiple functions.
Example
void functionA(int n)
{
if(n > 0)
functionB(n – 1);
}
void functionB(int n)
{
if(n > 0)
functionA(n – 1);
}
Explanation
• functionA() calls functionB().
• functionB() calls functionA().
• The recursion continues until the stopping condition is met.
• This is called indirect recursion.
Tail Recursion
Tail recursion is a type of recursion in which the recursive function call is the last statement executed in the function.
It is generally more efficient because some compilers can optimize tail-recursive functions.
Example
void countDown(int n)
{
if(n == 0)
return;
printf(“%d “, n);
countDown(n – 1);
}
Explanation
• countDown() calls itself as the last statement.
• No operation is performed after the recursive call.
• Tail recursion can improve performance.
• It is useful for recursive algorithms.
Advantages of Recursion
• Simplifies complex problems.
• Produces shorter and cleaner code.
• Useful for tree and graph traversal.
• Supports divide-and-conquer algorithms.
• Makes mathematical problems easier to solve.
Example Program
Program
#include <stdio.h>
int factorial(int n)
{
if(n <= 1)
return 1;
return n * factorial(n – 1);
}
int main()
{
int result = factorial(5);
printf(“Factorial = %d”, result);
return 0;
}
Output
Factorial = 120
Explanation
• factorial() is called with the value 5.
• The function keeps calling itself until n becomes 1.
• When the base case is reached, the function starts returning values.
• Each recursive call multiplies its value with the returned result.
• The final factorial of 5 is 120.
Key Points
• Recursion is a technique where a function calls itself.
• Every recursive function must have a base case.
• The base case prevents infinite recursion.
• Recursion is useful for solving complex problems.
• Direct, Indirect, and Tail Recursion are common types.
• Recursive functions use the function call stack.
• Recursion is widely used in algorithms and data structures.