Tail-Recursive Functions

A tail-recursive function is a recursive function in which the recursive call is the last statement that is executed by the function. So basically nothing is left to execute after the recursion call.

An example in C++

// An example of tail recursive function:

static void print(int n)
{
    if (n < 0)
        return;
    cout << " " << n;

    // The last executed statement is a recursive call:
    print(n - 1);
}

An example in JavaScript

function prints(n) {
    if (n < 0) {
        return;
    }
    console.log(n);

    // The last executed statement
    // is recursive call
    prints(n - 1);
}

Optimization of Tail-Recursive Functions

Tail-recursive functions are better than non-tail-recursive ones because they can be optimized by the compiler.

The idea used by compilers to optimize tail-recursive functions is simple. Since the recursive call is the last statement, there is nothing left to do in the current function, so creating another stack frame for the current function can be avoided by simply sending the control back to the beginning of the function either using a loop or goto statement.(See this for more details)

Can a non-tail-recursive function be written as tail-recursive to optimize it?

Consider the following function to calculate the factorial of n.

It is a non-tail-recursive function. Although it looks like a tail recursive at first look. If we take a closer look, we can see that the value returned by fact(n - 1) is used in fact(n). So the call to fact(n-1) is not the last thing done by fact(n).

#include <iostream>
using namespace std;

// Non-tail-recursive factorial function
unsigned int fact(unsigned int n)
{
    if (n <= 0)
        return 1;

    // Recursive call is not the last operation
    return n * fact(n - 1);
}

int main()
{
    // Testing the factorial function
    cout << fact(5);
    return 0;
}

The above function can be written as a tail-recursive function. The idea is to use one more argument and accumulate the factorial value in the second argument. When n reaches 0, return the accumulated value.

#include <iostream>
using namespace std;

// A tail recursive function to calculate factorial
unsigned factTR(unsigned int n, unsigned int a)
{
    if (n <= 1)
        return a;

    return factTR(n - 1, n * a);
}

// A wrapper over factTR
unsigned int fact(unsigned int n) { return factTR(n, 1); }

// Driver program to test above function
int main()
{
    cout << fact(5);
    return 0;
}