4

当我试图回答这个问题时，我遇到了一些奇怪的结果：如何提高递归方法的性能？

但你不需要阅读那篇文章。我将在这里给出相关的上下文。这可能看起来很长，但如果你通读一遍，实际上并没有那么复杂。我希望这对所有人来说都很有趣。对于上下文，

syra(n) = { 1 if n=1; 
            n + syra(n/2) if n is even; and 
            n + syra(3n+1) if n is odd
          }

和

syralen(n) = No. of steps to calculate syra (n)

例如， syralen(1)=1，syralen(2)=2 since we need to go two steps. syra(10) = 10 + syra(5) = 15 + syra(16) = 31 + syra(8) = 39 + syra(4) = 43 + syra(2) = 45 + syra(1) = 46。所以 syra(10) 需要 7 个步骤。所以syralen(10)=7

最后，

lengths(n) = syralen(1)+syralen(2)+...+syralen(n)

那里的问题海报试图计算lengths(n)

我的问题是关于 Op 发布的递归解决方案（这是该问题中的第二个片段）。我会在这里转发：

public class SyraLengths{

        int total=1;
        public int syraLength(long n) {
            if (n < 1)
                throw new IllegalArgumentException();
            if (n == 1) {
                int temp=total;
                total=1;
                return temp;
            }
            else if (n % 2 == 0) {
                total++;
                return syraLength(n / 2);
            }
            else {
                total++;
                return syraLength(n * 3 + 1);
            }
        }

        public int lengths(int n){
            if(n<1){
                throw new IllegalArgumentException();
            }
            int total=0;
            for(int i=1;i<=n;i++){
                total+=syraLength(i);
            }

            return total;
        }

        public static void main(String[] args){
            System.out.println(new SyraLengths().lengths(5000000));
        }
       }

当然是一种不寻常的（并且可能不推荐）递归方式，但它确实计算出正确的东西，我已经证实了这一点。我试图写一个更常见的递归版本：

public class SyraSlow {

    public long lengths(int n) {
        long total = 0;
        for (int i = 1; i <= n; ++i) {
            total += syraLen(i);
        }
        return total;
    }

    private long syraLen(int i) {
        if (i == 1)
            return 1;
        return 1 + ((i % 2 == 0) ? syraLen(i / 2) : syraLen(i * 3 + 1));
    }

现在这是奇怪的部分 - 我尝试测试上述两个版本的性能，例如：

public static void main(String[] args){
            long t1=0,t2=0;
            int TEST_VAL=50000;

            t1 = System.currentTimeMillis();
            System.out.println(new SyraLengths().lengths(TEST_VAL));
            t2 = System.currentTimeMillis();
            System.out.println("SyraLengths time taken: " + (t2-t1));

            t1 = System.currentTimeMillis();
            System.out.println(new SyraSlow().lengths(TEST_VAL));
            t2 = System.currentTimeMillis();
            System.out.println("SyraSlow time taken: " + (t2-t1));
        }

对于TEST_VAL=50000，输出为：

5075114
SyraLengths time taken: 44
5075114
SyraSlow time taken: 31

正如预期的那样（我猜），普通递归稍微好一些。但是当我更进一步并使用TEST_VAL=500000时，输出是：

62634795
SyraLengths time taken: 378
Exception in thread "main" java.lang.StackOverflowError
    at SyraSlow.syraLen(SyraSlow.java:15)
    at SyraSlow.syraLen(SyraSlow.java:15)
    at SyraSlow.syraLen(SyraSlow.java:15)

为什么？Java 在这里做了什么样的优化，SyraLengths 版本没有达到 StackOverflow（它甚至可以工作TEST_VAL=5000000）？我什至尝试使用基于累加器的递归版本，以防我的 JVM 进行一些尾调用优化：

private long syraLenAcc(int i, long acc) {
        if (i == 1) return acc;
    if(i%2==0) {
        return syraLenAcc(i/2,acc+1);
    }
    return syraLenAcc(i * 3 + 1, acc+1);
    }

但我仍然得到相同的结果（因此这里没有尾调用优化）。那么，这里发生了什么？

PS：如果您能想到任何标题，请编辑为更好的标题。

4

2 回答 2

2

使用原始版本，尾递归优化是可能的（在 JIT 内）。不过，不知道它是否真的发生过。但有可能原始版本在堆 [呃，我的意思是堆栈] 使用方面效率更高。（或者可能存在粗略检查不明显的功能差异。）

于 2012-06-04T20:06:05.110 回答
2

好吧，事实证明有一个简单的解释：

我long syraLen(int n)用作方法签名。但 的值n实际上可以远大于Integer.MAX_VALUE。所以syraLen得到负面的输入，这就是问题所在。如果我将其更改为long syraLen(long n)，则一切正常！我希望我也把if(n < 1) throw new IllegalArgumentException();原来的海报一样。本来可以节省我一些时间。

于 2012-06-05T15:05:12.327 回答