Lua中的尾调用优化

2012-11-9 6:44:14
收藏：0
阅读：112
评论：1

Lua声称它能正确实现尾调用优化，因此不需要为每个调用维护堆栈，从而允许无限递归。我尝试编写一个_sum_函数，一个是非尾调用，一个是尾调用：

非尾调用版本

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

print(sum(1000000))

出现预期的stackoverflow错误。

尾调用版本

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)

我认为在这种情况下不会出现stackoverflow，因为它是尾调用，但仍然因为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]: ?

因此，Lua是否真正支持尾调用优化，或者我的函数实际上不是尾调用？

我在redhat 5上使用的是lua 5.1.4。

点赞
用户1008957
用户1008957

Lua 中的尾递归 必须 符合以下格式：

return fct(args)

因此，你的尾递归版本必须重写如下：

function sum2(accu, n)
  if n > 0 then
    accu.value = accu.value + n
    return sum2(accu, n-1) --< 注意这里的 return
  end
end
2012-11-09 07:53:39

作者:

用户70198

用户70198
推荐文章