Web Analytics Made Easy - StatCounter

Tail Recursion

In order to fully understand the tail recursion, you need to understand how recursion works. Please read the following article first.

  1. Understanding Recursion

Introduction

Tail recursion, as the name suggests, is a type of recursion where no computation is done after the return of the recursive call. In other words, the function call happens as a last operation in the function body.

In the last post, we learned the traditional recursion. In traditional recursion, the recursive call returns some value and we use that returned value to do further operations. This means, every frame in the call stack must have a return address and they must return to that address after they finish the execution. The problem with this approach is that we can not calculate the final result until every recursive function return and as a result, we need to put all the stack frames in the call stack.

In tail recursion, the compiler can optimize the code and can reduce the number of call frames in the call stack. We will see next that only one stack frame is sufficient for the tail recursion to work effectively.

How tail recursion works?

Consider an example of the factorial function. The traditional recursion to calculate the factorial is shown below.

1
2
3
4
5
6
7
int fact(int n) {
    if (n == 0) {
        return 1;
    }

    return n * fact(n - 1);
}

We can clearly see that the function fact is not the last operation. After the function fact(n-1) returns, we multiply the returned value with n to get the required result. We need the result of previous function call to calculate the result of current function call and this requires that every function call should be pushed into the stack. The execution trace of this program for $5!$ is shown below

1
2
3
4
5
6
7
8
9
10
5 * fact(4)
5 * 4 * fact(3)
5 * 4 * 3 * fact(2)
5 * 4 * 3 * 2 * fact(1)
5 * 4 * 3 * 2 * 1 * fact(0)
5 * 4 * 3 * 2 * 1
5 * 4 * 3 * 2
5 * 4 * 6
5 * 24
120

From line number 5 - 9, the result from the previous function call is multiplied with current $n$ to get the result. There is no any place that compiler can optimize the code.

Can we re-design the code so that we do not need the result from previous function call to calculate the result of current function call? The answer is: yes we can and that is what we call TAIL recursion. The code below shows the tail-recursive version of the factorial function

1
2
3
4
5
6
7
8
9
#include 

int fact(int n, int result) {
    if (n == 0) {
        return result;
    }

    return fact(n - 1, n * result);
}

The code above shows that the function call fact(n - 1, n * result) is the last operation inside function fact(n, result). That means current function call does not need the result of the previous function call. This can be illustrated with the help of an execution trace for fact(5, 1) given below.

1
2
3
4
5
6
fact(5, 1)
fact(4, 5)
fact(3, 20)
fact(2, 60)
fact(1, 120)
120

After line 6, every function call in the call stack returns the same value, 120. The compiler can optimize this by removing all but one call frame (current frame) from the call stack.

Does all programming languages support tail-recursion?

The answer, unfortunately, is NO. Languages like C, C++, Python or JAVA do not support tail-recursion (Even though some compilers might support). Almost all functional programming languages like Haskel, Lua, LISP, Scheme, Erlang etc. support tail recursion.