递归计算中偶尔出现StackOverflowError

Question

在Eclipse中执行下面粘贴的代码时,我遇到以下异常大约有3次:

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”

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