在lua中的尾调用优化

发布时间：2020-12-15 00:24:22 所属栏目：大数据来源：网络整理

导读：Lua声称它正确地执行尾部调用,因此每个调用都不需要维护堆栈,因此允许无限递归,我试图写一个和函数,一个不是尾调用,一个是尾调用：非尾部版本 function sum(n) if n 0 then return n + sum(n-1) endendprint(sum(1000000)) stackoverflow如预期. 尾部版本 f

Lua声称它正确地执行尾部调用,因此每个调用都不需要维护堆栈,因此允许无限递归,我试图写一个和函数,一个不是尾调用,一个是尾调用：

非尾部版本

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上使用了lua 5.1.4

解决方法

Lua中的尾部呼叫必须具有以下形式

return fct(args)

所以你的尾呼叫版本必须重写为：

function sum2(accu,n)
  if n > 0 then
    accu.value = accu.value + n
    return sum2(accu,n-1) --< note the return here
  end
end

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!