Menu
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
343
Another interesting feature of functions in Lua is that they do proper tail calls. (Several authors use the term proper tail recursion, although the concept does not involve recursion directly.) After f calls g , it has nothing else to do.
In Lua you can write loops in a functional way with tail recursion.
Proper tail calls (PTC) is a programming language feature that enables memory-efficient recursive algorithms. Tail call optimization is where you can avoid allocating a new stack frame for a function because the calling function will simply return the value it gets from the called function.
Regarding functions call optimization, gcc can do tail-call elimination to save the cost of allocating a new stack frame, and tail recursion elimination to turn a recursive function to non-recursive iterative one.
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
