Proper Tail Recursion

wiki

Lua 5.0 implements proper tail recursion [1]. It means that for a special pattern of function calls, an optimization is done to save resources, namely the stack. This pattern is so that every time a function ends by returning the value of a function (including a recursive calls), the current stack frame is reused without need for consumption of stack resources. In pseudo code


function f(args)

    ...

    return g(args2)

end

Sometimes recursive functions can rewritten so that they are made into tail recursive versions. For example, the usual definition of the factorial function would leads us to:


function fact(n) if (n==0) then return 1 else return n*fact(n-1) end end

which is not tail recursion, because the last computation to do is the product of n and fact(n-1). But the following is


function factt(n) return fact_(n, 1) end



function fact_(n, ans) if (n==0) then return ans else return fact_(n-1, n*ans) end end

The results of the two definitions are rigorously the same, given the same arguments.


> = fact(5)

120

> = factt(5)

120

But the situation is different behind the scenes. We can raise this difference if we use the functions the way they were not designed to be. The naive implementations above only work for positive integers. They are expected to stray into infinite recursion if given negative or fractional results.

If we do fact(-1) we end with a stack overflow message:


> = fact(-1)

stdin:1: stack overflow

stack traceback:

        stdin:1: in function `fact'

        stdin:1: in function `fact'

        ...

        stdin:1: in function `fact'

        (tail call): ?

        [C]: ?

On the other hand, if we invoke factt(-1), it never returns (which is more akin to the mathematical analysis of the function body).

Proper tail recursion is about economy, which is very important for the kind of applications Lua is intented to. As an optimization, debugging is made harder as reconstruction of call traces are impossible.

Every time a language specification says that proper tail recursion is implemented, it means a promise that the stack will not be wasted in the special case of tail function calls. It is a contract for quality that language designers offer for users. It is largely usual in the computer science world: languages like Scheme, Perl, Forth also do this. Complain if your favourite programming language does not.

This is a starting text. It is meant to illustrate the feature as a Lua feature and may be mentioned in the function call tutorial.

RecentChanges · preferences
edit · history
Last edited November 17, 2003 1:52 am GMT (diff)