Tail Recursion and Head Recursion

What is Tail Recursion?

A recursive function is tail recursive when recursive call is the last thing executed by the function. For example the following Python function factorial() is tail recursive.

What is 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.

Tail recursion is just a particular instance of recursion, where the return value of a function is calculated as a call to itself, and nothing else.

# normal recursive of factorial
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

# tail recursive version of factorial
def tail_factorial(n, num=1):
    if n == 0:
        return num
    else:
        return tail_factorial(n - 1, num * n)
# head recursive version of factorial
def head_factorial(n, num=1):
    if n > 0:
        return head_factorial(n - 1, num * n)
    else:
        return num
# for loop version of factorial
def loop_factorial(n):
    num = 1
    for i in range(1, n + 1):
        num = num * i
    return num

Notice how, even though the return line of the first function contains a call to itself, it also does something to its output (in this particular case computing a product) so the return value is not really the recursive call’s return value. Usually we can make a regular recursive function tail recursive through the use of an accumulator parameter, as I did in the second declaration of factorial.

Why tail calls matter

Recursive tail calls can be replaced by jumps. This is called “tail call elimination” and is a transformation that can help limit the maximum stack depth used by a recursive function, with the benefit of reducing memory traffic by not having to allocate stack frames. Sometimes, recursive function which wouldn’t ordinarily be able to run due to stack overflow are transformed into function which can.

Introducing Tail Call Elimination

The whole idea behind Tail Call Elimination is avoiding function calls and stack frames as much as possible, since they take time and are the key difference between recursive and iterative programs. You read that right: Functional Languages are awesome, partly, because they found a way to call less functions.

In order to understand the next part, it’s important to go back a step and understand what exactly is going on every time we do a function call.

Because of the benefits, some compilers (like gcc) perform tail call elimination, replacing recursive tail calls with jumps (and, depending on the language and circumstances, tail calls to other functions can sometimes be replaced with stack massaging and a jump). In the following example, we will eliminate the tail calls in a piece of code which does a binary search. It has two recursive tail calls.

Time and space complexity of tail and head recursion:

Tail Recursion: Time complexity of a tail recursion is O(n) and space complexity is O(n)

Head Recursion: Time complexity of a head recursion is O(n) and space complexity is O(n)

Which one is better to use?

As we know from above section tail and head recursion has similar time and space complexity. In above code snippet we can see that I mentioned a for loop version of that recursive function to get n th factorial. So if it is possible to convert a tail or head loop into a loop then you should go for loop because it’s space complexity is lower than tail or head recursion. For above loop function it took O(1) space complexity.

GitHub Link: Tail and Head Recursion