Proper Tail Recursion 

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(n1) end end
which is not tail recursion, because the last computation to do is the product of n
and fact(n1)
. 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_(n1, n*ans) end end
The results of the two definitions are rigorously the same, given the same arguments.
> = fact(5) 120 > = factt(5) 120But 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.