Functional Programming: A PragPub Anthology

Recursion in Lua

Recursive functions eventually call themselves, like this:

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

print(factorial(5))   --> 120

Easy to follow, but executing this function for some values of n will result in a stack overflow error. That’s because on each successive invocation of factorial(n - 1), the machine must retain a reference to the previous iteration on its stack. The stack is finite, so it eventually runs out of space and the program explodes:

print(factorial(-1))

lua: factorial.lua:5: stack overflow
stack traceback:
    factorial.lua:5: in function 'factorial'
    factorial.lua:5: in function 'factorial'
    ...

Lua 5.0 added proper tail calls, a sort of functional ...