Lua claims that it implement tail call properly thus no stack needs to be maintained for each call thus allow infinite recursion, I tried to write a sum function, one is not tail call, and one is tail call:
non tailcall version
function sum(n)
if n > 0 then
return n + sum(n-1)
end
end
print(sum(1000000))
stackoverflow as expected.
tailcall version
function sum2(accu, n)
if n > 0 then
accu.value = accu.value + n
sum2(accu, n-1)
end
end
local accu = {value = 0}
sum2(accu, 1000000)
print(accu.value)
I suppose there would be no stackoverflow in this case as it is a tailcall, but it still failed due to stackoverflow:
/bin/lua/5.1.4/bin/lua: tailcall.lua:13: stack overflow
stack traceback:
tailcall.lua:13: in function 'sum2'
tailcall.lua:13: in function 'sum2'
tailcall.lua:13: in function 'sum2'
tailcall.lua:13: in function 'sum2'
tailcall.lua:13: in function 'sum2'
tailcall.lua:13: in function 'sum2'
tailcall.lua:13: in function 'sum2'
tailcall.lua:13: in function 'sum2'
tailcall.lua:13: in function 'sum2'
tailcall.lua:13: in function 'sum2'
...
tailcall.lua:13: in function 'sum2'
tailcall.lua:13: in function 'sum2'
tailcall.lua:13: in function 'sum2'
tailcall.lua:13: in function 'sum2'
tailcall.lua:13: in function 'sum2'
tailcall.lua:13: in function 'sum2'
tailcall.lua:13: in function 'sum2'
tailcall.lua:13: in function 'sum2'
tailcall.lua:17: in main chunk
[C]: ?
So is lua really support tail call optimization, or my function is actually not tail call here?
I am using lua 5.1.4 on redhat 5
Tail call in Lua must have the following form
return fct(args)
So your tail call version must be rewritten as:
function sum2(accu, n)
if n > 0 then
accu.value = accu.value + n
return sum2(accu, n-1) --< note the return here
end
end