In this article, we will be in depth discussing about Non-Tail Recursion. The basic algorithm, its time complexity, space complexity, advantages and disadvantages of using a non-tail recursive function in a code.

Table of contents:

1. Introduction
2. Types of recursion
3. Non-Tail Recursion
4. Time and Space Complexity
5. Comparison between Non-Tail Recursion and Loop
6. Tail Recursion vs. Non-Tail Recursion
7. Which one should I use?
8. Conclusion

Introduction

In a program, recursion is realized by using a mechanism that pushes the function and variables required for calculation to the call stack each time the function is called, and pops it when the function evaluation is completed.

Types of recursion

First, let me introduce that there are different types of recursion.
There are six types of recursion:

• Non-Tail Recursion (head recursion)
• tail recursion
• Direct Recursion
• Indirect Recursion
• Linear recursion
• Tree Recursion

In this article at OpenGenus, we will only be learning about non-tail recursion and have a comparison between tail recursive and non-tail. Also seeing which one is better.

Non-Tail Recursion

Non-tail Recursion is defined as a recursive function in which the first statement is a recursive call and then the other operations are performed.

It is also called Head Recursion.

Non-tail Recursion does not perform any operation at the time of recursive calling. Instead, all operations are done at the return time.

Let us take an example of Non-tail Recursion and understand how its done:

void fun(int n)
{
    if (n>0){
        fun(n-1);
        printf (" %d", num);
    }
}

From the above program it is clear that first we are calling the recursive function and then printing will be done at returning time.
So, the function doesn't perform any operation at the calling time.
This can also be said as the basic definition of non-tail recursion.

Time and Space Complexity

The above is a recursive relation and by Master's theorem,
Time Complexity = O(n)

Also, we know that in recursion we use an implicit stack as it grows in memory which each call the function makes.
Space Complexity = O(n)

Comparison between Non-Tail Recursion and Loop

We know that every recursion can be expressed in loops. And non-tail recursion is no exception to this.
Its just that converting a non-tail recursion to loop is a bit different and not too simple.
The below example will clear the above statement.

//Non-tail Recursion
void fun(int n)
{
    if (n>0){   //conditional statement
        fun(n-1);  
        printf (" %d", num);
    }
}

Now the above can be written using while loop :

void fun(int n)
{
    int i=1;
    while(i<=n)   //looping statement
    {
        printf (" %d", i);
        i++;
    }
}

Both the programs will give the same output.

The reason we convert a recursive function to a looping statement because while the program shows the same time complexity O(n). the looping statement exhibit space complexity O(1).
Making loops more efficient than non-tail recursion.

Tail Recursion vs. Non-Tail Recursion

A function is tail-recursive if it ends by returning the value of the recursive call.
Tail recursion has the recursive statement in the last part of the program and no other operations are executed later.

In “non-tail recursion”, there are still operations to be performed after the recursive call since the recursive statement is the first statement.

Which one should I use?

Now that you know there are two types of recursion. I'm sure you're wondering which one to use, so I'd like to share some exemplary facts.
We should prefer to use recursion as long as we know it has better time complexity than non-tail recursion.
And here's why.

Tail recursion is computationally less expensive than non-tail recursion.
Also modern compilers such as in C++, Java uses compiler's code optimization better known as tail call optimization or elimination. Using a set of rule based operation while compiling the code, it converts the tail recursion into iterative code automatically and so saves space.

Conclusion

We have learned about non-tail recursion. Non-Tail recursion is a type of recursive call in programming which is also the first statement of the program and then the operations are performed.

We also discussed the code to convert non-tail recursion into a looping function.
We also saw the difference between tail recursion and non-tail recursion and why tail recursion is better to use.