Types of Recursion
Published by: Anil K. Panta
Types of Recursion
Recursion is a programming technique where a function calls itself to solve smaller parts of a problem. There are different types of recursion based on how and when the function calls are made.
Let’s explore all types of recursion with simple C programs and examples.
1. Direct Recursion
Definition:
When a function calls itself directly, it is called direct recursion.
It can be further divided into:
Tail Recursion
Head Recursion
Tree Recursion
Nested Recursion
A. Tail Recursion
Definition: If the recursive call is the last statement in the function (i.e., nothing happens after it), it’s called tail recursion.
Example: Print numbers from n to 1
#include <stdio.h>
void fun(int n) {
if (n > 0) {
printf("%d ", n);
fun(n - 1); // Last statement = Tail recursion
}
}
int main() {
fun(3);
return 0;
}
Output: 3 2 1
Time Complexity: O(n)
Space Complexity: O(n)
Loop Version of Tail Recursion
void fun(int y) {
while (y > 0) {
printf("%d ", y);
y--;
}
}
Output: 3 2 1
Space Complexity (Loop): O(1) — More efficient than recursion
B. Head Recursion
Definition: If the recursive call is the first statement in the function, it's called head recursion. The work is done after the function returns.
Example: Print numbers from 1 to n
#include <stdio.h>
void fun(int n) {
if (n > 0) {
fun(n - 1); // First statement = Head recursion
printf("%d ", n);
}
}
int main() {
fun(3);
return 0;
}
Output: 1 2 3
Time Complexity: O(n)
Space Complexity: O(n)
C. Tree Recursion
Definition: When a function calls itself more than once, it's called tree recursion. It forms a tree-like structure of calls.
Example:
#include <stdio.h>
void fun(int n) {
if (n > 0) {
printf("%d ", n);
fun(n - 1);
fun(n - 1);
}
}
int main() {
fun(3);
return 0;
}
Output: 3 2 1 1 2 1 1
Time Complexity: O(2ⁿ)
Space Complexity: O(n)
D. Nested Recursion
Definition: A recursive function passes the result of another recursive call as its argument — recursion inside recursion.
Example:
#include <stdio.h>
int fun(int n) {
if (n > 100)
return n - 10;
return fun(fun(n + 11));
}
int main() {
printf("%d\n", fun(95));
return 0;
}
Output: 91
Time Complexity: Complex
Space Complexity: Depends on how deep recursion goes
2. Indirect Recursion
Definition: When two or more functions call each other in a circular manner, it is called indirect recursion.
Example:
#include <stdio.h>
void funB(int n); // Function declaration
void funA(int n) {
if (n > 0) {
printf("%d ", n);
funB(n - 1);
}
}
void funB(int n) {
if (n > 1) {
printf("%d ", n);
funA(n / 2);
}
}
int main() {
funA(20);
return 0;
}
Output: 20 19 9 8 4 3 1
Time Complexity: Depends on input
Space Complexity: Depends on depth of calls
Summary Table of Recursion Types
Final Thought:
Recursion helps solve complex problems by breaking them into smaller parts. Understanding different types of recursion is key to becoming a strong programmer.
Use tail recursion for easier optimization
Use head or tree recursion when breaking down problems
Know when a loop might be more efficient
