Lua和Java中的递归

2013-7-25 5:30:5
收藏：0
阅读：143
评论：2

我有一个递归算法（有三种不同形式），可以计算前n个奇数的和。这些算法仅用于学习，我知道有更好的方法解决这个问题。我已经用Lua和Java编写了这三个变量，分别称为Lua 1、Lua 2、Lua 3和Java 1、Java 2、Java 3。前两个非常相似，只是重新排列了一下。

Lua程序在这里，Java程序在这里。

Lua 1和2表现非常出色，可以轻松达到n = 100,000,000。当n> 16,000时，Lua 3会导致堆栈溢出。

Java 1只能达到n = 4000，然后导致堆栈溢出，而Java 2可以达到9000。Java 3在再次导致堆栈溢出之前，可以到达n = 15,000。

有人能解释这些结果吗？为什么Java 1、2和3的表现如此糟糕，而Lua 1和2的表现如此出色？

点赞
用户57695
用户57695

Java 不是为递归算法设计的。特别是它不支持常见的优化，如尾调用优化。

Java 更适合使用循环，通常更快，并且使用简单的循环很简单。

如果使用迭代和 Deque，则应该没有 n 值的限制。

当运行非常低效的代码时，您往往会发现一个情况或另一个情况可以优化它，而低效率的改善可能会产生很大的差异。

更高效的一种方法是

// 计算前 n 个正奇数的和的函数
public static long sumOdds(long n) {
    long sumAll = n * (n + 1)/2;
    long sumEven = n/2 * (n/2 + 1);
    return sumAll - sumEven;
}
public static void main(String[] args) throws Exception {
    sumOdds(1);

    long start = System.nanoTime();
    long l = sumOdds(Integer.MAX_VALUE);
    long time = System.nanoTime() - start;
    System.out.printf("sumOdds(%,d) took %,d ns%n", Integer.MAX_VALUE, time);
}

输出结果如下：

sumOdds(2,147,483,647) took 343 ns
2013-07-25 00:03:33
用户1009479
用户1009479

Lua进行尾调用优化。例如，像这样的函数：

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仍然需要在返回之前进行计算，因此不存在适当的尾调用。

2013-07-25 02:21:19

作者:

用户1516403

用户1516403
推荐文章