java - 递归计算中偶发的StackOverflowError

Question

在 Eclipse 中执行下面粘贴的代码时，大约有三分之一的时间我会遇到以下异常:

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)*

另外 2 次，它按预期吐出结果(每次运行之间的时间略有不同):

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”

如果该配置不够，请尝试更大的堆栈。