Lua中的尾调用优化

Question

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

- Baiyan Huang

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

- prapin

---

哦，是的 - 这正是原因！只是多了一个“回车”，谢谢prapin！ - Baiyan Huang

但是Lua怎么可能想不到这实际上是一个尾调用呢 :) - Baiyan Huang

“Lua怎么可能没意识到这实际上是一个尾调用？”我不明白你刚才问的是什么。 - Nicol Bolas

@NicolBolas，我认为我知道原因了。对于Lua而言，'sum2(accu, n-1)' 和 'sum2(accu, n-1); return' 是一样的，而不是'return sum2(accu, n-1)'，因此显然没有返回来说这并非一个尾调用。 - Baiyan Huang

如《Lua编程》第1部分第6章所述，为了被视为尾调用，返回语句应直接跟在函数调用后面，而不是任何表达式。因此：return n+sum(n-1)在Lua中被理解为n与sum(n-1)的结果之间的操作。为了成为尾调用，Lua期望返回值直接是一个函数调用。请注意：return somefunc(n+1)在这种情况下，Lua将其理解为带有参数n+1的调用，因此作为尾调用进行处理。 - Arkt8