What is Recursion?
The process in which a function calls itself directly or indirectly is called recursion
and the corresponding function is called a recursive function. Using recursive
algorithm, certain problems can be solved quite easily. Examples of such
problems are Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals,
DFS of Graph, etc.
Types of Recursions:
Recursion are mainly of two types depending on whether a
function calls itself from within itself or more than one function
call one another mutually. The first one is called direct recursion
and another one is called indirect recursion. Thus, the two types
of recursion.
2
Direct Recursion: These can be further categorized
into four types:
Tail Recursion: If a recursive function calling itself and that recursive call is the last
statement in the function then it’s known as Tail Recursion. After that call the recursive
function performs nothing. The function has to process or perform any operation at the
time of calling and it does nothing at returning time.
void fun(int n)
{
if (n > 0) {
Printf(“%d\n”,n);
// Last statement in the function
fun(n - 1);
}
}
3
Head Recursion: If a recursive function calling itself and that recursive call is the first statement in
the function then it’s known as Head Recursion. There’s no statement, no operation before the call.
The function doesn’t have to process or perform any operation at the time of calling and all
operations are done at returning time.
void fun(int n)
{
if (n > 0) {
// First statement in the function
fun(n - 1);
Printf(“%d\n”,n);
}
}
4
If a recursive function calling itself for one time then it’s known as Linear Recursion.
fun(n)
{
// some code
if(n>0)
{
fun(n-1); // Calling itself only once
}
// some code
}
5
Tree Recursion: To understand Tree Recursion let’s first understand Linear Recursion. If a recursive function
calling itself for one time then it’s known as Linear Recursion. Otherwise if a recursive function calling itself
for more than one time then it’s known as Tree Recursion.
void fun(int n)
{
if (n > 0)
{
// Calling once
fun(n - 1);
// Calling twice
fun(n - 1);
}
}
6
Nested Recursion: In this recursion, a recursive function will pass the parameter as a recursive
call. That means “recursion inside recursion”.
int fun(int n)
{
if (n > 100)
return n - 10;
// A recursive function passing parameter
// as a recursive call or recursion inside
// the recursion
return fun(fun(n + 11));
}
7
Indirect Recursion: In this recursion, there may be more than one functions and they are calling one another in a circular manner.
void funA(int n)
{
if (n > 0) {
Printf(“%d\n”,n);
// fun(A) is calling fun(B)
funB(n - 1);
}
}
void funB(int n)
{
if (n > 1) {
Printf(“%d\n”,n);
// fun(B) is calling fun(A)
funA(n / 2);
}
}
