How to optimize non-tail recursion?

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.

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.