Tail recursion

In Lua you can write loops in a functional way with tail recursion. However there is a certain restriction, so you should do tail call properly.

To do tail call properly you should write return statement as a single value statement. Let's see some examples:

function sum(n)
    if n > 0 then
        return n + sum(n - 1)
    else
        return 0
    end
end

print(sum(10))

55

Alright, that works. However there is a problem. Look at the tail call:

return n + sum(n - 1)

This statement operates on two values. The first argument n should be kept until sum(n - 1) return a value. Which means stack frame cannot be discarded before the tail call: there is still something we need in future. Let's try it with a bigger value:

function sum(n)
    if n > 0 then
        return n + sum(n - 1)
    else
        return 0
    end
end

print(sum(1000000))

input:3: C stack overflow

As you see, Lua compiler couldn't optimize our tail call which caused stack overflow. To fix that we should rewrite it in a single-value return statement:

function sum(n, accum)
    if n > 0 then
        return sum(n - 1, accum + n)
    else
        return accum
    end
end

print(sum(1000000, 0)) -- Don't forget about the initial accum value

Instead of keeping addition arguments on the stack, we use an accumulator as a function parameter. Now we don't need to keep anything on every level of stack, so stack frames can be discarded. And now it works properly:

500000500000