<p>Tail recursion, where a function calls itself as the last step, is straightforward to optimize as to prevent unbounded stack growth: <a href="https://en.wikipedia.org/wiki/Tail_call#Implementation_methods" rel="noreferrer">tail call optimization</a> applies.</p>
<p>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).</p>
<p>How could one go about optimizing non-tail recursion to reduce stack usage?</p>

<implementation><optimization><recursion>
How to optimize non-tail recursion?
CC BY-SA 4.0
2023-07-13T01:42:59.403Z
The obvious, if less than useful, answer if you only care about stack usage: do everything in the heap :p
rydwolf
CC BY-SA 4.0
2023-07-13T06:37:01.177Z
I note that the question presupposes a falsehood. It is always *possible* to rewrite a function into a tail recursive function. It is often very inconvenient, but inconvenient and impossible are different. A function can be transformed into an equivalent continuation passing program, and in continuation passing style *every* call is a tail call.
Eric Lippert
CC BY-SA 4.0
2023-07-13T06:39:48.787Z
If that's not clear, an example might help. I go through an example of transforming a short Python program with a recursion in the middle into CPS here: https://ericlippert.com/2018/12/17/removing-a-recursion-in-python-part-2/
Eric Lippert
<h2>Last call modulo constructor</h2>
<p>One common situation in declarative languages is where there is <em>almost</em> 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.</p>
<p>An especially common occurrence is where the only thing remaining is a <em>constructor</em>. Consider, for example, list <code>append</code> in ML:</p>
<pre class="lang-ocaml prettyprint-override"><code>fun append [] l2     = l2
  | append (h::t) l2 = h :: append t l2;
</code></pre>
<p>The only thing that happens after the recursive call to <code>append</code> is the construction of the cons cell. So this could be implemented as a tail call or loop where the constructor occurs <em>before</em> the call, and a reference or pointer is passed to the tail call.</p>
<p>You may need to implement this as a worker/wrapper, with the wrapper satisfying the language's ABI. In a hypothetical C-like backend:</p>
<pre class="lang-c prettyprint-override"><code>ml_object*
ml_append(ml_object* l1, ml_object* l2)
{
    ml_object* return_value = nullptr;
    ml_append_worker(l1, l2, &amp;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-&gt;car = l1-&gt;car;
        return_value-&gt;cdr = nullptr; /* Garbage collection needs to know about this! */
        /* The following is now a tail call. */
        ml_append_worker(l1-&gt;cdr, l2, &amp;return_value-&gt;cdr);
    }
}
</code></pre>
<p>As with all worker/wrapper arrangements, the wrapper is an excellent candidate for inlining.</p>
<h2>Middle recursion</h2>
<p>A second option is what Mercury calls <a href="https://www.sciencedirect.com/science/article/pii/S0743106696000684" rel="noreferrer">middle recursion</a>. Using Mercury's terminology, this pattern:</p>
<pre class="lang-c prettyprint-override"><code>a_function()
{
    if (is_base_case()) {
        base_case();
    }
    else {
        down();
        a_function();
        up();
    }
}
</code></pre>
<p>...can be transformed into this, using an explicit stack.</p>
<pre class="lang-c prettyprint-override"><code>a_function()
{
    while (!is_base_case()) {
        down();
        push_local_variables_onto_stack();
    }
    base_case();
    while (stack_has_elements) {
        pop_local_variables_off_stack();
        up();
    }
}
</code></pre>
<p>The stack can sometimes be replaced by a counter if the data stored across the recursive call is trivial or nonexistent.</p>
<p>A common hand-implementation of quick sort essentially does this, using an explicit stack for one recursive call and a loop for the other.</p>

CC BY-SA 4.0
2023-07-13T03:10:40.053Z
2023-07-13T03:10:40.053Z
Pseudonym
CC BY-SA 4.0
2023-07-13T03:35:53.887Z
For the first variant, the keyword to search for would be "Tail Call Modulo `CONS`".
Jörg W Mittag
<p>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.</p>
<p>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.</p>
<p>For mutual recursion you will need to inline one function into the other one.</p>

CC BY-SA 4.0
2023-07-13T01:32:50.400Z
2023-07-13T01:32:50.400Z
ratchet freak
# How to optimize non-tail recursion?
Posted by: username_0 on 2023-07-13
Tail recursion, where a function calls itself as the last step, is straightforward to optimize as to prevent unbounded stack growth: [tail call optimization](https://en.wikipedia.org/wiki/Tail_call#Implementation_methods) 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?
**Tags:** implementation optimization recursion
> **Comments:**
> **username_1**: The obvious, if less than useful, answer if you only care about stack usage: do everything in the heap :p  
> **username_2**: I note that the question presupposes a falsehood. It is always *possible* to rewrite a function into a tail recursive function. It is often very inconvenient, but inconvenient and impossible are different. A function can be transformed into an equivalent continuation passing program, and in continuation passing style *every* call is a tail call.  
> **username_2**: If that's not clear, an example might help. I go through an example of transforming a short Python program with a recursion in the middle into CPS here: https://ericlippert.com/2018/12/17/removing-a-recursion-in-python-part-2/  
---
## 2 answers
### Answer by username_3 on 2023-07-13. Score: 6
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.
> **Comments:**
> **username_4** (2023-07-13): For the first variant, the keyword to search for would be "Tail Call Modulo `CONS`".  
---
### Answer by username_5 on 2023-07-13. Score: 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.
---
