<h2>Motivation</h2>
<p>I have implemented the tail recursion optimization for my language, where a <code>return</code> statement calls itself by <code>goto</code> instead of pushing arguments onto the stack.</p>
<p>But for general recursion, for example:</p>
<pre class="lang-js prettyprint-override"><code>function factorial(n: Integer) {
    if n &lt;= 1 {
        1
    } else {
        n * factorial(n - 1);
    }
}
</code></pre>
<p>Here <code>n * factorial(n - 1)</code> does not directly call the function itself, so the tail recursion optimization cannot be directly applied, and it is easy for the user to use this function to overflow the stack.</p>
<h2>Question</h2>
<p>I'm wondering if there is a catch-all way to detect whether a function can be written tail-recursive, and output its tail-recursive form if possible?</p>

<optimization><tail-call-optimization>
Tail-recursive detection and conversion
CC BY-SA 4.0
2023-07-05T07:42:16.213Z
CPS transform will turn all your calls into tail calls.
SK-logic
CC BY-SA 4.0
2023-07-05T17:52:38.053Z
How is it that "Here n * factorial(n - 1) does not directly call the function itself"?  To me, factorial is being very explicitly and obviously called, the argument just changes to (n-1).
JosephDoggie
CC BY-SA 4.0
2023-07-05T18:13:01.783Z
@JosephDoggie In order to be tail recursive, the function would have to return the result of the recursive call without doing anything else with it. In this case, it first multiplies the result by `n` before returning the product. That extra step is what "not directly" refers to in this context.
DLosc
<p>You need to check that the top level expression node in the return statement is only a call.</p>
<p>in your example in that factorial example after you parse it into an AST you have</p>
<pre><code>return  
    mul 
        param (n), 
        call
            factorial, 
            sub
                param (n), 
                const(1)
</code></pre>
<p>The expression node in the return statement is a mul, therefore you cannot (simply) transform this into a tail call.</p>
<p>If we rewrite the function to use an accumulator instead:</p>
<pre><code>function factorial(n: Integer, result : Integer = 1) {
    if n &lt;= 1 {
        result
    } else {
        factorial(n - 1, result * n);
    }
}
</code></pre>
<p>this results in</p>
<pre><code>return  
    call
        factorial, 
        sub
            param (n), 
            const(1)
        mul
            param (result)
            param (n)
</code></pre>
<p>and then the conversion from <code>return call</code> into <code>tailcall</code> is trivial</p>

CC BY-SA 4.0
2023-07-05T08:38:03.340Z
2023-07-05T08:38:03.340Z
ratchet freak
CC BY-SA 4.0
2023-07-05T08:44:42.743Z
This kind of rewriting is effective, but I want to know how to automatically find the result to be added under normal circumstances? In some cases, one parameter may not be enough, and more memory parameters are needed. How to judge how many are needed?
Aster
CC BY-SA 4.0
2023-07-05T08:49:40.590Z
This particular rewrite assumes the post recursion operation is associative, but in general you cannot assume that especially if the post recursion operation is more complicated
ratchet freak
<p>Check your CFG. The required conditions are:</p>
<ul>
<li>There's only one recursive invocation</li>
<li>It takes place in a block immediately preceding the end.</li>
</ul>
<p>That would by definition mean tail recursion, as well as allow you to unroll it in a clear way in terms of this very CFG.</p>
<p>I wouldn't recommend trying to perform this optimization earlier, as in an AST it is significantly less clear, with the recursive call being possibly hidden inside several nested scopes.</p>

CC BY-SA 4.0
2023-07-12T07:11:09.497Z
2023-07-12T07:11:09.497Z
abel1502
<p>It is technically always possible to turn a recursive function into a tail recursive one by maintaining a separate, heap-allocated stack. For example, you could write your <code>factorial</code> function this way:</p>
<pre class="lang-js prettyprint-override"><code>function factorial(n: Integer) {
  let frames = new Stack&lt;Integer&gt;();

  function go(n: Integer) {
    if n &lt;= 1 {
      let result = 1;
      while (!frames.isEmpty()) {
        result = frames.pop() * result;
      }
      return result;
    } else {
      frames.push(n);
      return go(n - 1);
    }
  }

  return go(n);
}
</code></pre>
<p>This uses constant stack space. However, this transformation is not very useful, as it just moves the memory into the heap. If your language supports growing the stack on stack overflow, it’s likely more efficient to just store the context on the call stack.</p>
<p>However, this may not be what you’re looking for. After all, it’s possible to write <code>factorial</code> in way that uses constant space:</p>
<pre class="lang-js prettyprint-override"><code>function factorial(n: Integer) {
  function go(acc: Integer, n: Integer) {
    if n &lt;= 1 {
      return acc;
    } else {
      return go(acc * n, n - 1);
    }
  }
  return go(1, n);
}
</code></pre>
<p>Perhaps it seems like there ought to be some way to automatically obtain this version of <code>factorial</code> from the one in your question. However, in general this is not the case, as this translation only works because multiplication is associative and the base case is multiplication’s identity! If this were not the case, the two functions would do different things:</p>
<ul>
<li><p>Using the version in your question, <code>factorial(5)</code> computes <code>5 * (4 * (3 * (2 * 1)))</code>.</p>
</li>
<li><p>Using the tail-recursive version I gave above, <code>factorial(5)</code> computes <code>(((1 * 5) * 4) * 3) * 2</code>.</p>
</li>
</ul>
<p>Since the equivalence of these expressions relies on a binary operation that is associative and has an identity, you could in theory do a transformation of this sort for any <a href="https://en.wikipedia.org/wiki/Monoid" rel="noreferrer">monoid</a>. But this seems like probably more trouble than it’s worth, especially since it would be difficult for programmers to predict when the optimization would happen. In languages that implement proper tail calls, programmers know that if they want constant stack usage, they must write a tail recursive function; they don’t expect the compiler to make it tail recursive for them.</p>

CC BY-SA 4.0
2023-07-05T07:32:04.363Z
2023-07-05T07:32:04.363Z
Alexis King
CC BY-SA 4.0
2023-07-05T07:46:52.390Z
1.It may be possible to specify the addition of the `rec` keyword to use this optimization, but it is still very strange, because since the programmer has realized that this can be written as tail recursion, then he can choose the appropriate memoization parameters for tail recursion. Otherwise he just trying luck to see if the compiler is smart enough, it doesn't make any sense to add `rec`.
Aster
CC BY-SA 4.0
2023-07-05T07:47:29.703Z
2.It seems that only a single parameter can be simplified to a stack, multi-parameter is more complex, I think it might be a tuple map, such as `f(a, b) = f(a - 1, b) + f(a, b - 1); 0 if a==0 || b==0;`
Aster
CC BY-SA 4.0
2023-07-05T07:53:16.400Z
@Aster Yes, each of the frames in your heap-allocated stack has to be able to hold all of the variables that would otherwise be stored in the stack-allocated frame.
Alexis King
CC BY-SA 4.0
2023-07-05T20:33:10.907Z
IIRC, [Continuation−Passing Style‚ Defunctionalization‚ Accumulations‚ and Associativity](https://www.cs.ox.ac.uk/jeremy.gibbons/publications/continued.pdf) by Jeremy Gibbons is a good reference and source of further examples backing up this answer.
James Wood
# Tail-recursive detection and conversion
Posted by: username_0 on 2023-07-05
Motivation
I have implemented the tail recursion optimization for my language, where a return statement calls itself by goto instead of pushing arguments onto the stack.
But for general recursion, for example:
function factorial(n: Integer) {
    if n <= 1 {
        1
    } else {
        n * factorial(n - 1);
    }
}

Here n * factorial(n - 1) does not directly call the function itself, so the tail recursion optimization cannot be directly applied, and it is easy for the user to use this function to overflow the stack.
Question
I'm wondering if there is a catch-all way to detect whether a function can be written tail-recursive, and output its tail-recursive form if possible?
**Tags:** optimization tail-call-optimization
> **Comments:**
> **username_1**: CPS transform will turn all your calls into tail calls.  
> **username_2**: How is it that "Here n * factorial(n - 1) does not directly call the function itself"?  To me, factorial is being very explicitly and obviously called, the argument just changes to (n-1).  
> **username_3**: @JosephDoggie In order to be tail recursive, the function would have to return the result of the recursive call without doing anything else with it. In this case, it first multiplies the result by `n` before returning the product. That extra step is what "not directly" refers to in this context.  
---
## 3 answers
### Answer by username_6 on 2023-07-05. Score: 13 | Accepted answer
It is technically always possible to turn a recursive function into a tail recursive one by maintaining a separate, heap-allocated stack. For example, you could write your factorial function this way:
function factorial(n: Integer) {
  let frames = new Stack();

  function go(n: Integer) {
    if n <= 1 {
      let result = 1;
      while (!frames.isEmpty()) {
        result = frames.pop() * result;
      }
      return result;
    } else {
      frames.push(n);
      return go(n - 1);
    }
  }

  return go(n);
}

This uses constant stack space. However, this transformation is not very useful, as it just moves the memory into the heap. If your language supports growing the stack on stack overflow, it’s likely more efficient to just store the context on the call stack.
However, this may not be what you’re looking for. After all, it’s possible to write factorial in way that uses constant space:
function factorial(n: Integer) {
  function go(acc: Integer, n: Integer) {
    if n <= 1 {
      return acc;
    } else {
      return go(acc * n, n - 1);
    }
  }
  return go(1, n);
}

Perhaps it seems like there ought to be some way to automatically obtain this version of factorial from the one in your question. However, in general this is not the case, as this translation only works because multiplication is associative and the base case is multiplication’s identity! If this were not the case, the two functions would do different things:

Using the version in your question, factorial(5) computes 5 * (4 * (3 * (2 * 1))).

Using the tail-recursive version I gave above, factorial(5) computes (((1 * 5) * 4) * 3) * 2.


Since the equivalence of these expressions relies on a binary operation that is associative and has an identity, you could in theory do a transformation of this sort for any monoid. But this seems like probably more trouble than it’s worth, especially since it would be difficult for programmers to predict when the optimization would happen. In languages that implement proper tail calls, programmers know that if they want constant stack usage, they must write a tail recursive function; they don’t expect the compiler to make it tail recursive for them.
> **Comments:**
> **username_0** (2023-07-05): 1.It may be possible to specify the addition of the `rec` keyword to use this optimization, but it is still very strange, because since the programmer has realized that this can be written as tail recursion, then he can choose the appropriate memoization parameters for tail recursion. Otherwise he just trying luck to see if the compiler is smart enough, it doesn't make any sense to add `rec`.  
> **username_0** (2023-07-05): 2.It seems that only a single parameter can be simplified to a stack, multi-parameter is more complex, I think it might be a tuple map, such as `f(a, b) = f(a - 1, b) + f(a, b - 1); 0 if a==0 || b==0;`  
> **username_6** (2023-07-05): @Aster Yes, each of the frames in your heap-allocated stack has to be able to hold all of the variables that would otherwise be stored in the stack-allocated frame.  
> **username_7** (2023-07-05): IIRC, [Continuation−Passing Style‚ Defunctionalization‚ Accumulations‚ and Associativity](https://www.cs.ox.ac.uk/jeremy.gibbons/publications/continued.pdf) by Jeremy Gibbons is a good reference and source of further examples backing up this answer.  
---
### Answer by username_4 on 2023-07-05. Score: 3
You need to check that the top level expression node in the return statement is only a call.
in your example in that factorial example after you parse it into an AST you have
return  
    mul 
        param (n), 
        call
            factorial, 
            sub
                param (n), 
                const(1)

The expression node in the return statement is a mul, therefore you cannot (simply) transform this into a tail call.
If we rewrite the function to use an accumulator instead:
function factorial(n: Integer, result : Integer = 1) {
    if n <= 1 {
        result
    } else {
        factorial(n - 1, result * n);
    }
}

this results in
return  
    call
        factorial, 
        sub
            param (n), 
            const(1)
        mul
            param (result)
            param (n)

and then the conversion from return call into tailcall is trivial
> **Comments:**
> **username_0** (2023-07-05): This kind of rewriting is effective, but I want to know how to automatically find the result to be added under normal circumstances? In some cases, one parameter may not be enough, and more memory parameters are needed. How to judge how many are needed?  
> **username_4** (2023-07-05): This particular rewrite assumes the post recursion operation is associative, but in general you cannot assume that especially if the post recursion operation is more complicated  
---
### Answer by username_5 on 2023-07-12. Score: 1
Check your CFG. The required conditions are:

* There's only one recursive invocation
* It takes place in a block immediately preceding the end.

That would by definition mean tail recursion, as well as allow you to unroll it in a clear way in terms of this very CFG.

I wouldn't recommend trying to perform this optimization earlier, as in an AST it is significantly less clear, with the recursive call being possibly hidden inside several nested scopes.
---
