lua中的尾调用优化

Question

Lua声称它正确地实现了尾调用，因此每次调用都不需要维护堆栈，从而允许无限递归，我尝试编写一个sum函数，一个不是尾调用，一个是尾调用：

非尾调用版本

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

print(sum(1000000))

stackoverflow 正如预期的那样。

tailcall版本

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)

我想在这种情况下不会出现堆栈溢出，因为它是尾部调用，但由于堆栈溢出它仍然失败：

/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

Answer 1

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

Answer 2

正如已经说过的，唯一正确的尾部调用语法是

return f(...)

那是因为

f() ; return

与

return f()

不同：前者需要在调用

f

后进行最终操作：删除其结果以确保不返回任何内容。

但是lua怎么可能看不出这实际上是一个尾调用

因为lua是一种非常“动态”的语言：在

function sum2(accu, n)
    if n > 0 then
        accu.value = accu.value + n
        sum2(accu, n-1)
    end
end

sum2

不是调用 本身，而是调用 全局变量

"sum2"

（或者等效的 upvalue，如果声明为

local

） 这个变量可能会成为一个返回值的函数，在这种情况下发出尾部调用字节码将是不正确的。

换句话说：

f

是否进行尾调用是编译器无法访问的知识，只能在运行时确认，除非你使用牢不可破的语法

return f(...)