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