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在返回之前还需要进行计算，所以没有合适的尾调用。