Types of recursion with example

Recursion is a process in which a function calls itself again and again. We use recursion to solve bigger problem by dividing it into smaller similar sub-problems and then call them recursively.

Types of Recursion

Recursive functions can be classified on the basis of

a) Based on functions call itself – Direct / Indirect
b) Based on pending operation at each recursive call – Tail Recursive/ Head Recursive
c) Based on the structure of the function calling pattern – Linear / Tree

Based on functions call itself – Direct / Indirect

Direct Recursion

If a function calls itself from within itself is known as Direct Recursion.
When the method invokes itself it is direct.

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.

Indirect Recursion

In Indirect Recursion, more than one function call one another mutually in a circular manner.
For example, if a function ‘fun1()’ , calls function ‘fun2()’, which calls function ‘fun3()’ which again leads to ‘fun1()’ being invoked is called indirect recursion.

#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;
}

Based on pending operation at each recursive call – Tail Recursive/ Head Recursive

Tail / Bottom Recursion

Tail Recursion is an example of Direct Recursion, If a recursive function is calling itself and that recursive call is the last statement in the function then it’s known as Tail Recursion.
We can also say that if no operations are pending when the recursive function returns to its caller.
It is an efficient method as compared to others, as the stack space required is less and even compute overhead will get reduced.
After the call, the recursive function performs nothing.

#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;
}

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

Head/Top Recursion

Tail Recursion is an example of Direct Recursion, If a recursive function is calling itself and that recursive call is the first statement in the function then it’s known as Head Recursion.
Nothing will perform before calling of a recursive function.

#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;
}

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

Based on the structure of the function calling pattern – Linear / Tree

Linear Recursion

A linear recursive function is a function that only makes a single call to itself each time the function runs.
Our Factorial recursive function is a suitable example of linear recursion as it only involves multiplying the returned values and no further calls to the function.

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 
}

Tree recursion

In Tree recursion, Instead of a single function call there are two recursive calls for each non-base case.
Functions with two recursive calls are referred to as binary recursive functions.
In Tree recursion, there are pending operations that involve another recursive call to the function.

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));
}

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

Nested Recursion

In Nested recursion, a recursive function will be pass as the parameter in a recursive function itself.
That means “recursion inside 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;
}

[wpusb]

Types of recursion with example