java - Lua 与 Java 中的递归

Question

我有一个递归算法(三种不同的形式)，它计算前 n 个奇数正整数的总和。这些算法仅供学习，我知道有更好的方法来解决这个问题。我用 Lua 和 Java 编写了这三个变体，我将其称为 Lua 1、Lua 2、Lua 3 和 Java 1、Java 2 和 Java 3。前两个非常相似，只是重新排列。

Lua程序是here ，Java 程序是 here .

Lua 1 和 2 的性能非常好，可以轻松达到 n = 100,000,000。 Lua 3 遇到堆栈溢出，其中 n > 16,000。

Java 1 在遇到堆栈溢出之前只能达到 n = 4000，而 Java 2 则达到 9000。Java 3 在再次遇到堆栈溢出之前设法达到 n = 15,000。

谁能解释一下这些结果？为什么 Java 1、2、3 表现这么差，而 Lua 1、2 表现那么好？

Answer 1

Lua 确实 tail-call elimination 。例如，这样的函数:

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

无论您调用的 n 值是什么，都不会导致堆栈溢出。

在 Lua 中，只有采用 return func(args) 形式的调用才是尾调用，就像前两个 Lua 程序所做的那样。但在第三个Lua程序中:

return (sumOdds3(n-1)) + (2*n - 1)

Lua在返回之前仍然需要进行计算，因此没有适当的尾部调用。