How to optimize non-tail recursion?

Question

Tail recursion, where a function calls itself as the last step, is straightforward to optimize as to prevent unbounded stack growth: tail call optimization applies.

However, this doesn't apply to functions that recurse in the middle of their implementation, and then do more work with the result of the recursive call. While some such functions can be arranged to be tail-recursive, that's not always possible, especially for functions that call themselves more than once (e.g. a function that traverses a tree).

How could one go about optimizing non-tail recursion to reduce stack usage?

Answer 1

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.

Answer 2

If we can assume there is only 1 recursive call then you add a stack of stackframe structs. Then whenever a recursive call happens you push a copy of all local variables to the stack and then replace the parameters and goto the beginning of the function. On a return you pop the copy of the stackframe back into local variables and goto just after the original call site.

When there are 2 call sites you add an indicator of which callsite the recursion happened to the stackframe data and then goto the correct return point.

For mutual recursion you will need to inline one function into the other one.