Last call modulo constructor

One common situation in declarative languages is where there is almost a tail call, in the sense that there are no computations or calls (or ABI infrastructure, such as exception-handling code) between the call and the return.

An especially common occurrence is where the only thing remaining is a constructor. Consider, for example, list append in ML:

fun append [] l2     = l2
  | append (h::t) l2 = h :: append t l2;

The only thing that happens after the recursive call to append is the construction of the cons cell. So this could be implemented as a tail call or loop where the constructor occurs before the call, and a reference or pointer is passed to the tail call.

You may need to implement this as a worker/wrapper, with the wrapper satisfying the language's ABI. In a hypothetical C-like backend:

ml_object*
ml_append(ml_object* l1, ml_object* l2)
{
    ml_object* return_value = nullptr;
    ml_append_worker(l1, l2, &return_value);
    return return_value;
}

void
ml_append_worker(ml_object* l1, ml_object* l2, ml_object** return_value)
{
    if (is_nil(l1)) {
        *return_value = l2;
    }
    else {
        *return_value = make_cons();
        return_value->car = l1->car;
        return_value->cdr = nullptr; /* Garbage collection needs to know about this! */
        /* The following is now a tail call. */
        ml_append_worker(l1->cdr, l2, &return_value->cdr);
    }
}

As with all worker/wrapper arrangements, the wrapper is an excellent candidate for inlining.

Middle recursion

A second option is what Mercury calls middle recursion. Using Mercury's terminology, this pattern:

a_function()
{
    if (is_base_case()) {
        base_case();
    }
    else {
        down();
        a_function();
        up();
    }
}

...can be transformed into this, using an explicit stack.

a_function()
{
    while (!is_base_case()) {
        down();
        push_local_variables_onto_stack();
    }
    base_case();
    while (stack_has_elements) {
        pop_local_variables_off_stack();
        up();
    }
}

The stack can sometimes be replaced by a counter if the data stored across the recursive call is trivial or nonexistent.

A common hand-implementation of quick sort essentially does this, using an explicit stack for one recursive call and a loop for the other.

Consider a simple function that adds the first N natural numbers. (e.g. sum(5) = 0 + 1 + 2 + 3 + 4 + 5 = 15).

Here is a simple JavaScript implementation that uses recursion:

function recsum(x) {
    if (x === 0) {
        return 0;
    } else {
        return x + recsum(x - 1);
    }
}

If you called recsum(5), this is what the JavaScript interpreter would evaluate:

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + (1 + recsum(0)))))
5 + (4 + (3 + (2 + (1 + 0))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15

Note how every recursive call has to complete before the JavaScript interpreter begins to actually do the work of calculating the sum.

Here's a tail-recursive version of the same function:

function tailrecsum(x, running_total = 0) {
    if (x === 0) {
        return running_total;
    } else {
        return tailrecsum(x - 1, running_total + x);
    }
}

Here's the sequence of events that would occur if you called tailrecsum(5), (which would effectively be tailrecsum(5, 0), because of the default second argument).

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

In the tail-recursive case, with each evaluation of the recursive call, the running_total is updated.

Note: The original answer used examples from Python. These have been changed to JavaScript, since Python interpreters don't support tail call optimization. However, while tail call optimization is part of the ECMAScript 2015 spec, most JavaScript interpreters don't support it).