Recursion

When a called function calls itself again inside it's body of code, it is called as recursion and the function that does this is called as the recursive function.

Recursions are classified into two types:
1. Direct Recursion
2. Indirect Recursion

In this part of Recursion, we will talk only about Direct Recursion. But before we do so, we need to know the two phases of a recursive function which are:

1. Calling Phase

When an action is performed before the recursive function has called itself, that action is said to have been performed during the Calling Phase because the function is YET to call itself recursively.

2. Returning Phase

When an action is performed after the statement inside the recursive function that calls itself then that action is said to have been performed during the Returning Phase because the function is RETURNING after calling itself.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
void recursivePrint(int n)
{
    if(n!=0)
    {
        cout << "Calling Phase" <<endl;
        recursivePrint(n-1)+n;
        cout << "Returning Phase" << endl;
    }  
    else
    {
        return;
    } 
}

In the above function, "Calling Phase" is printed before the function as called itself again and hence it is performed in the Calling Phase while "Returning Phase" will be printed in the Returning Phase because the function would then be returning after calling itself and that would be when 'n==0'.

Direct Recursion

In this type of recursion, a recursive function calls ITSELF to create the recursiveness. This is further divided into four main categories and they are:
1. Tail Recursion
2. Head Recursion
3. Tree Recursion
4. Nested Recursion

1. Tail Recursion

When the process of calling itself is the LAST step inside a recursive function and there are no more actions to perform after the calling -itself step it is known as Tail Recursion. 

To memorize it, we can say that this is called as TAIL recursion because it is the last step in a recursive function similar to how tail is the last part of an animal's body.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
void recursivePrint(int n)
{
    if(n!=0)
    {
        cout << n << " ";
        recursivePrint(n-1);                                 
    }  
    else
    {
        return;
    } 
}

To make things more clear, it is necessary to note that even the following code is not an example of tail recursion:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
void recursivePrint(int n)
{
    if(n!=0)
    {
        cout << n << " ";
        recursivePrint(n-1)+n;                     
    }  
    else
    {
        return;
    } 
}

And that is because the '+n' is performed during the returning phase and not during the calling phase.


2. Head Recursion

Similar to tail recursion is Head Recursion. If the calling-itself step is the FIRST step in the body of a recursive function (after passing the conditional statement) and there are no actions to be performed before that then it is called as Head Recursion.

This type of recursion is named Head recursion because similar to how head is the first part of an animal, the calling-itself is the first statement in the recursive function.

3. Tree Recursion

When a recursive function calls itself more than once then it is called as tree recursion.There can be any number of statements or actions to be performed before, after and in-between the calling-itself steps.

Now, this is named so because when we trace the recursion, it forms a tree like structures. 

4. Nested Recursion

When a recursive function calls itself by taking a recursive function as parameter then it is called as a Nested Recursion.