8
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ CPS transform will turn all your calls into tail calls. $\endgroup$
    – SK-logic
    Commented Jul 5, 2023 at 7:42
  • $\begingroup$ 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). $\endgroup$ Commented Jul 5, 2023 at 17:52
  • 2
    $\begingroup$ @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. $\endgroup$
    – DLosc
    Commented Jul 5, 2023 at 18:13

3 Answers 3

13
$\begingroup$

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<Integer>();

  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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Aster
    Commented Jul 5, 2023 at 7:46
  • $\begingroup$ 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; $\endgroup$
    – Aster
    Commented Jul 5, 2023 at 7:47
  • $\begingroup$ @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. $\endgroup$
    – Alexis King
    Commented Jul 5, 2023 at 7:53
  • $\begingroup$ IIRC, Continuation−Passing Style‚ Defunctionalization‚ Accumulations‚ and Associativity by Jeremy Gibbons is a good reference and source of further examples backing up this answer. $\endgroup$
    – James Wood
    Commented Jul 5, 2023 at 20:33
3
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$
    – Aster
    Commented Jul 5, 2023 at 8:44
  • 2
    $\begingroup$ 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 $\endgroup$ Commented Jul 5, 2023 at 8:49
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .