Types of Recursion with Example

Recursion is a way of solving problems where a function calls itself to do smaller parts of the same problem.

Instead of solving a big problem all at once, we break it into smaller, similar problems. Then, the function solves each small problem by calling itself again and again. This continues until we reach the base case, which is the simplest version of the problem that can be solved directly. After solving the smallest problem, the answers from all the smaller parts are combined step by step to solve the original big problem.

In short, recursion is like solving a big task by repeating the same steps on smaller pieces until it becomes very easy.

Types of Recursion

Recursive functions can be classified on the basis of

1. Based on functions call itself – Direct / Indirect
2. Based on pending operation at each recursive call – Tail Recursive/ Head Recursive
3. Based on the structure of the function calling pattern – Linear / Tree

Based on functions call Itself

1. Direct Recursion

Direct Recursion happens when a function calls itself directly from inside its own code. In other words, if a function wants to solve a problem and, as part of its steps, it calls itself again, this is called direct recursion. The function keeps calling itself until it reaches a base case, which is the simplest version of the problem that can be solved without calling itself.

int func(int num) {
  if (num == 0)
    return 1;
  else
    return func(num - 1);
}

Here, function ‘func’ is calling itself. This is an example of direct recursion.

2). Indirect Recursion

Indirect Recursion is a type of recursion where two or more functions call each other in a circular manner instead of calling themselves directly. For example, if fun1() calls fun2(), then fun2() calls fun3(), and finally fun3() calls fun1() again, this cycle continues until a base case is reached in one of the functions that stops the recursion. In simple words, indirect recursion happens when functions keep calling each other in a loop to solve a problem.

#include <stdio.h>
  
void fun2(int n);
  
void fun1(int n)
{
    if (n > 0) {
        printf("%d ", n);
        fun2(n - 1);
    }
}
  
void fun2(int n)
{
    if (n > 1) {
        printf("%d ", n);
        fun1(n - 2);
    }
}
  
int main()
{
    fun1(10);
    return 0;
}

The above program is an example of indirect recursion, where two functions call each other in a loop. The program starts by calling fun1(10). fun1() checks if the number is greater than 0, prints it, and then calls fun2() with a smaller number. fun2() checks if the number is greater than 1, prints it, and calls fun1() again with an even smaller number. This process continues, with the number getting smaller each time, until the conditions in the functions are no longer true. At that point, the recursion stops. The output of this program is the numbers printed in this order: 10 9 7 6 4 3 1.

Based on Pending Operation

1. Tail / Bottom Recursion

Tail Recursion is a type of direct recursion where a function calls itself as the last step in the function. This means that after the recursive call, the function does nothing else before returning. In other words, no extra work is left to do when the function comes back from the recursive call. Tail recursion is more efficient than normal recursion because it uses less memory on the stack and reduces computation overhead. Since nothing is done after the call, the function can be optimized by the compiler, making it faster and saving space.

#include <stdio.h>
void fun(int n)
{
    if (n > 0) {
        printf("%d ", n); 
        fun(n - 1);  // Last statement in the function
    }
}
  
int main()
{
    fun(5);
    return 0;
}

The above C program is an example of tail recursion. The function fun() calls itself at the last step after printing the number. It starts with fun(5), prints 5, and then calls fun(4). This continues, printing 4, 3, 2, 1 in order, until n becomes 0. When n is 0, the function stops calling itself and the recursion ends. It is called tail recursion because nothing is done after the recursive call, making it efficient and using less memory. The output of the program is: 5 4 3 2 1.

Time Complexity For Tail Recursion: O(n)
Space Complexity For Tail Recursion: O(n)

2. Head/Top Recursion

Head Recursion is a type of direct recursion where a function calls itself at the beginning of the function, before doing anything else. This means that the function does not perform any operations until the recursive call finishes. In other words, all the work is done after returning from the recursive calls. Since the function keeps calling itself first, the recursion goes deep before any action is taken, and the operations are executed in reverse order as the function returns back. Head recursion is different from tail recursion, where the function does its work before the recursive call.

#include <stdio.h> 
void fun(int n)
{
    if (n > 0) {        
        fun(n - 1); // First statement in the function 
        printf("%d ", n);
    }
}
  
int main()
{
    fun(5);
    return 0;
} 

This C program is an example of head recursion. In the function fun(), the recursive call comes first, before printing anything. When we start with fun(5), the function keeps calling itself with smaller numbers (fun(4), fun(3), fun(2), fun(1)) until n becomes 0. Only after reaching 0 do the functions start returning one by one, and at that time, each function prints its number. This means the numbers are printed in ascending order: 1 2 3 4 5. It is called head recursion because the recursive call happens at the beginning, and nothing is done before it.

Time Complexity For Head Recursion: O(n)
Space Complexity For Head Recursion: O(n)

Based on the structure of the function

1. Linear Recursion

A linear recursive function is a function that calls itself only once each time it runs. This means the recursion happens in a straight line, one step at a time, without multiple branches or calls. A common example is the factorial function, where the function multiplies the current number by the result of the factorial of the smaller number. In this case, there is only one recursive call at each step, and no additional calls are made, which makes it a clear example of linear recursion.

Below is an example of Linear Recursion

int factorial(int n) 
{ 
    if (n==1) 
        return 1;           //base case, as we know that factorial of 1 is 1 
    else
        return n*factorial(n-1);    //recursive case 
} 

This C function calculates the factorial of a number using recursion. It is an example of linear recursion because the function calls itself only once in each step.

Here’s how it works:

1. Base Case: If n == 1, the function returns 1, because the factorial of 1 is 1. This stops the recursion.
2. Recursive Case: If n > 1, the function returns n * factorial(n-1). This means it multiplies the current number n by the factorial of the smaller number (n-1).

The function keeps calling itself with smaller numbers until it reaches 1. Then, all the returned values are multiplied step by step to give the final factorial.

For example, factorial(4) works like this:

factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1  // base case

Finally: 4 * 3 * 2 * 1 = 24.

2. Tree recursion

Tree Recursion is a type of recursion where a function makes more than one recursive call in each step instead of just one. Most commonly, it makes two recursive calls, which is why such functions are also called binary recursive functions. In tree recursion, after making the first recursive call, there are still pending operations, which include another recursive call. This creates a branching structure, like a tree, where each call can lead to multiple new calls. Because of these multiple calls, tree recursion grows very fast compared to linear recursion.

Below is an example of Tree Recursion

#include <stdio.h>
void fun(int n)
{
    if (n > 0) {
        printf("%d ", n); 
        fun(n - 1); //calling first time
        fun(n - 2); //calling second time
    }
}
 
int main()
{
    fun(10);
    return 0;
}
 
Fibonacci series is also a example of tree/binary recursion
 
 
int fibonacci(int i){ 
    if(i==0) return 0; 
    else if(i==1) return 1; 
    else return (fibonacci(i-1)+fibonacci(i-2));
} 

The first program is an example of tree recursion, where the function fun() makes two recursive calls for each number greater than 0: fun(n-1) and fun(n-2). When fun(10) is called, it prints 10 and then calls fun(9) and fun(8). Each of these calls again makes two more calls, creating a branching structure like a tree. The recursion stops when n <= 0, which is the base case.

Similarly, the Fibonacci function is also an example of tree or binary recursion. To calculate fibonacci(i), the function makes two recursive calls: one for i-1 and one for i-2. These calls continue recursively, forming a binary tree of calls. The base cases i == 0 and i == 1 stop the recursion. Because each step generates multiple calls, tree recursion grows quickly and uses more memory compared to linear recursion.

Time Complexity For Tree Recursion: O(2^n)
Space Complexity For Tree Recursion: O(n)

3. Nested Recursion

Nested Recursion is a type of recursion where a recursive function is used as an argument to itself. In other words, the function calls itself inside another call of the same function, creating a “recursion inside recursion” situation. This means that before one call can complete, it may need to solve another recursive call as its parameter, making the recursion more complex than linear or tree recursion.

Example of Nested Recursion

#include <stdio.h>
int fun(int n)
{
    if (n > 100)
        return n - 10;
  
    // A recursive function is passes as parameter
    // in recursive function itself or recursion
    // inside the recursion
    return fun(fun(n + 11));
}
  
int main()
{
    fun(50);
    printf("%d", r);
    return 0;
}

This program is an example of nested recursion, where a recursive function is called as a parameter to itself, creating “recursion inside recursion.” In the function fun(int n), if n > 100, it returns n - 10 as the base case. Otherwise, it calls itself like this: fun(fun(n + 11)). This means that before the outer call can complete, the function must first compute the inner call fun(n + 11). For example, calling fun(50) will lead to fun(fun(61)), then fun(fun(72)), and so on, until n + 11 becomes greater than 100. Once the base case is reached, all the nested calls start returning step by step, eventually giving the final result. Nested recursion is more complex than linear or tree recursion because each call depends on the result of another recursive call.