递归计算中的偶然StackOverflowError

Question

在执行Eclipse中粘贴的代码时，大约每3次中就有1次遇到以下异常：

Exception in thread "main" java.lang.StackOverflowError
    at src.Adder.recursiveSumAllNumbersUpTo(Driver.java:33)
    at src.Adder.recursiveSumAllNumbersUpTo(Driver.java:37)
    ... *(there are 1024 lines in this stack)*

另外两次，它按预期输出结果(每次运行的次数略有变化)：

Recursive: 467946
Non Recursive: 61282
Difference between recursive and non-recursive: 406664
Sum from recursive add: 19534375
Sum from non-recursive add: 19534375

为什么例外只发生在30%的时间里？

下面是代码：

public class Driver {

    public static void main(String[] args) {

        Adder adder = new Adder();
        int valueToSumTo = 6250;

        long startTime = System.nanoTime();
        int raSum = adder.recursiveAddAllNumbersUpTo(valueToSumTo);
        long endTime = System.nanoTime();
        long raDif = endTime - startTime;
        System.out.println("Recursive: " + (raDif));

        startTime = System.nanoTime();
        int nonRaSum = adder.nonRecursiveAddAllNumbersUpTo(valueToSumTo);
        endTime = System.nanoTime();
        long nonRaDif = endTime - startTime;
        System.out.println("Non Recursive: " + (nonRaDif));

        System.out.println("Difference between recursive and non-recursive: " + (raDif - nonRaDif));
        System.out.println("Sum from recursive add: " + raSum);
        System.out.println("Sum from non-recursive add: " + nonRaSum);
    }
}

class Adder {

    public int recursiveAddAllNumbersUpTo(int i) {

        if (i == 1) {
            return i;
        }

        return i + recursiveAddAllNumbersUpTo(i - 1);
    }

    public int nonRecursiveAddAllNumbersUpTo(int i) {
        int count = 0;
        for(int num = 1; num <= i; num++) {
            count += num;
        }

        return count;
    }   
}

Answer 1

每次递归方法调用自己时，所有东西都会进入堆栈，像您这样的算法需要一个非常深的堆栈。

要解决您的问题，您应该增加您的堆栈大小。

您可以通过使用-Xss参数调用JVM来做到这一点。

如果您正在使用Eclipse，您可以通过执行以下操作来做到这一点：

1. 右键单击您的项目->运行为->运行配置；
2. 转到参数选项卡；在VM参数处，编写："-Xss4m“

如果配置不够，尝试一个更大的堆栈。

Answer 2

试着看看是否有用：

来自(http://www.odi.ch/weblog/posting.php?posting=411)

Java堆栈大小神话 Java使用堆栈的方式基本上没有文档化。因此，我们的开发人员只能自己找出答案。今天，我编写了一些有趣的测试代码，它提供了令人惊讶的结果。在我的测试中，我在RedHat EnterpriseLinux3下使用了Sun。 首先，我想知道VM为线程选择的堆栈大小。我发现ulimit -s参数对VM选择的堆栈大小没有直接影响。缺省值显然是512 is，可以使用-Xss和-XX:ThreadStackSize参数自由更改。但我找不到这些参数在行为上的区别。他们似乎也在做同样的事情。此外，我发现这个Linux机器能够以每秒5000次的速度创建新线程。 我通过创建新线程并将它们设置为阻塞等待调用来执行这些测试。我一直在创建线程，直到VM内存用完为止。对于512 k堆栈，线程数约为3700,256 k堆栈约为7300,128 k约为13700。 这导致堆栈消耗以下内存: 3700 x 512 to =1850 to 7300 x 256 to=1825 to 13700 x 128 to=1713 to。 当然，32位进程仅限于4GB的地址空间(内核为-1或2GB)。因此，内存接近这2GB减去堆大小，这是很自然的。(请注意，堆栈从未从堆中分配。) 接下来，我测试了在堆栈溢出之前可以调用递归方法的深度。我通过修改初始程序来做到这一点，这样每个线程都会恢复到一个方法中，直到它到达堆栈溢出，然后进入休眠状态。线程记录最大递归深度。所以我才得到了很奇怪的结果。特别是在服务器VM中，最大深度在1750到5700次调用(128 k堆栈)之间变化很大！这远远不是固定不变的，这可能是我的第一猜测。对于客户机VM，数量通常较低，但变化不大:在1100到1650之间。 此外，最大深度似乎在测试开始时较低，并在接近尾声时增加。

Answer 3

使用堆栈大小：-Xss32m允许堆栈为32 Mo。

注意: AFAIK，java不处理(为什么？！)尾部递归优化。