In this article, we will look into the different types of Recursion generally seen in programming to solve various problems. We will look at description of each type with example through code for better understanding.
First of all, let’s have a quick recap of Recursion. In general, Recursion is an approach to solve problems where the solution depends on the solutions of smaller instances or sub-problems of the same problem. So, in Programming A function that calls itself repeatedly (can be one time call) is called a Recursive Function.
Types of Recursion
Recursion or Recursive Functions in programming paradigm can be classified mainly into 2 types:
- Direct Recursion
- Indirect Recursion
Let us look at each type and their examples:
Direct Recursion
Direct Recursion occurs when a function explicitly calls the same function again. This is the simplest form of recursion. This is again subdivided into 3 types:
1. Tail Recursion
Tail Recursion occurs if a recursive function calls itself (Direct Recursion) and the function call is the last statement or step to be processed in the function before returning having reached the base case. After processing the call the function returns control back to the parent function call. It is during the time of function call the operations happen.
Let us look at the sample code to have a clear understanding:
//Program to Show use of Tail Recursion
#include <stdio.h>
// Tail Recursive function
void fun(int n)
{
// base case
if(n==0)
return;
else
{
printf("Hello World! \n");
// Last statement in the function
fun(n - 1);
}
}
// Main Function
int main()
{
int n = 5;
fun(n);
return 0;
}
Output:
Hello World! Hello World! Hello World! Hello World! Hello World!
This is a simple code in C, we pass n=5 in the function fun, each time we print a statement and call for function with value n-1. The function terminates when n=0, this is the Base Case of our Recursive function. We can see the call is the last step in the function. The function prints “Hello World!” 5 times.
This is also an example of a popular question asked in some interviews ‘Print Your Name N times Without Loop’. As you can see recursion comes in handy in solving this type of problem because without using a loop we can print any statement by calling function N times.
2. Non-Tail Recursion
A recursive function is said to be Non-Tail, if the recursive call to the same function is not the last statement or the last step processed by the function. After returning back from the call stack there is some code left to evaluate. In the case, of a function, the recursive call is the first statement to be processed by the function such type of recursion is termed as Head Recursion because it is the first call and there is no recursive call before it.
Note: Tail-recursive functions are considered far better than non-tail recursive functions as they can be further optimized by the compiler. Since the recursive call is the last statement, there is nothing left to do in the current function, so the compiler does not save the current function call in the call stack.
Let’s look at the example of Non-Tail Recursion in code:
//Program to Show Non-Tail Recursion
#include <stdio.h>
// Non-Tail Recursive function
void nonTail(int n)
{
// base case
if(n==0)
return;
// The recursive call is not the last staement in the function
nonTail(n - 1);
printf("%d \n",n);
}
// Main Function
int main()
{
int n = 5;
nonTail(n);
return 0;
}
Output:
1 2 3 4 5
This is a simple implementation in C, we pass n=5 in the function fun, each time call for function with value n-1 without printing it at first. As a result, fun(1) will be the first to execute completely and 1 is printed first. The function calls terminate when n=0, this is the Base Case of our Recursive function. We can see the call is not the last step in the function. The program above demonstrates Given a Number N Print 1 to N without Loop.
3. Tree Recursion
The recursion in which the function calling itself calls for one more than time inside it’s block, is called a Tree Recursion. If the call is made only once inside the function block then, it is termed as Linear Recursion. A famous example of this type of recursion is in Nth Fibonacci Number problem, where given a number we have to find the nth term value in Fibonacci series.
Let us have a look at the code for the above example:
//Program to generate Nth Fibonacci Number showing Tree-Recursion
#include<stdio.h>
int fib(int n)
{
// Base Case
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}
void main()
{
int n = 4;
printf("%d", fib(4));
}
Output:
3
In this above code, we print the Nth Fibonacci number. Let us have a clear understanding with the help of a recursive tree diagram.
The Recursion Tree is shown above, we call the function fib(4) which generates two more calls fib(3) and fib(2) , fib(2) makes a call for fib(1), and fib(0) which falls under our base case the sum of their returned value (1) is returned to parent fib(2). Similarly, for fib(3) it makes a call for fib(2) and fib(1), fib(1) falls under base case fib(2) follows the same procedure the sum (2) is returned to fib(3). At last, the sum of fib(2) and fib(3) is returned to the main parent call fib(4) giving 3 as our output.
Note: The Time Complexity of Tree Recursion is exponential as we see the growth of Tree doubles with each addition of each recursive call. Hence, the complexity is O(2n), when n calls are made.
Indirect Recursion
Indirect Recursion or Mutual Recursion is a unique type of recursion. A function (fun1) is said to be Indirectly recursive if it calls another function (say fun2) and then the other function (fun2) calls the previous function (fun1) again directly or indirectly. In such a case, both fun1 and fun2 are indirectly recursive. In this type of recursion, there may be more than one function calling one another in a cyclic way.
Note: The Base Cases for this type of function must be handled very carefully otherwise it may result in Stack Overflow Error.
Let us have a look at the implementation of the above in C:
//Program to Show Indirect Recursion
#include<stdio.h>
int n=1;
// Declaring function prototypes.
void fun1();
void fun2();
// defining recursive functions
void fun1()
{
if (n <= 20)
{
printf("%d ",n); // prints n
n++; // increments n by 1
fun2(); // calls foo2()
}
}
void fun2()
{
if (n <= 20)
{
printf("%d ",n); // prints n
n++; // increments n by 1
fun1(); // calls foo1()
}
}
//Main Function
int main()
{
fun1();
return 0;
}
Output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
The above code prints natural numbers from 1 to 20. The use of Indirect Recursion is shown above. We maintain a global variable n after printing the value of n we increment it and call the other function. The call for both functions terminates when n >20 is true.
So that’s it for the article, you can try out the above discussed examples with code in your C Compiler or online for your better understanding.
Feel free to leave your suggestions or doubts (if any) in the comments section below.