Java递归中的堆栈溢出错误

Question

我正在尝试编写一段代码来返回200万以下所有质数的总和。我有一个isPrime(int x)方法，如果数字是质数，则返回true。代码如下：

public static boolean isPrime(int x) {

        for (int i = 2; i < x; i++) {

            if (x % i == 0) {
                return false;
            }

        }
        return true;

    }

另一种方法是我正在尝试递归实现，但只能处理到某个特定的数字，超过这个数字会导致堆栈溢出错误。目前我成功运行该代码的最高数字是10,000。

以下是代码：

public static int sumOfPrimes(int a) {

    if (a < 2000000) {  //this is the limit

        if (isPrime(a)) {
            return a + sumOfPrimes(a + 1);

        } else {
            return sumOfPrimes(a + 1);
        }

    }
    return -1;
}

那么当数字变大时，为什么会出现堆栈溢出错误，我该如何处理它？此外，您通常如何处理编写针对如此庞大数字的代码？例如：像这样的普通数字操作，但针对更大的数字？我以递归方式编写了此代码，因为我认为这样会更有效率，但它仍然无法正常工作。

- ninesalt

---

你听说过埃拉托斯特尼筛法吗？ - Konstantin Yovkov

你甚至没有真正使用递归... 你意识到你的代码实际上在做什么吗？我非常怀疑。花了我几分钟才理解它，所以我不惊讶你遇到问题。可以说，这个程序并不是你想象中的那样运行。 - Xaver Kapeller

这甚至不是适合使用递归的问题。无论您在循环中遇到了什么问题，那都是开始的地方。您现在所拥有的与任何解决方案都非常远，修复它并不是正确的方法。 - Xaver Kapeller

@Swailem95，你怎么使用这个方法？你会传入0作为参数吗？你应该意识到，你传入的参数作为下限，并决定从哪一点开始累加质数，对吧？ - Xaver Kapeller

@XaverKapeller 是的，我知道。我把0传递给它。我告诉过你，对于较小的数字它运行良好。如果我漏掉了什么，你可以直接告诉我，而不是指出你认为有问题的一切。 - ninesalt

Answer 1

你的 isPrime 函数效率低下，不必要遍历到 x ，只需遍历到其平方根即可。

但这并不是你的解决方案失效的原因。递归深度不能超过一百万。

我会使用 埃拉托色尼筛法 迭代地解决这个问题，并在结果为布尔数组上进行循环。

- Tawcharowsky

Answer 2

一般来说，如果您仍然希望使用递归，可以使用尾递归。在递归中，每个函数调用将推送一些数据到堆栈中，而堆栈是有限的，因此会生成堆栈溢出错误。在尾递归中，您不会将任何内容推送到堆栈中，因此不会引发异常。

基本上，您所需要做的就是将先前计算的数据作为参数发送，而不是将其放在堆栈中。

所以：

function(int x) {
    // end condition
    return function(x - 1) + x;
}

"使用尾递归将是："

function (int max, int curr, int prev, int sum) {
    if (curr > max) 
        return sum;

    return function (max, curr + 1, curr, sum + curr)
}

请记住，这只是伪代码而不是真正的Java代码，但足够接近Java代码。

欲了解更多信息，请查看

什么是尾递归？

- user4233758

---

Java不支持尾递归。 - Prashant

Answer 3

使用埃拉托斯特尼筛法：

以下是通过埃拉托斯特尼方法找到小于或等于给定整数n的所有质数的算法：

1）创建一个由2到n的连续整数列表：（2、3、4、…、n）。
2）最初，让p等于2，即第一个质数。
3）从p开始，以p为增量计数，并在列表中标记大于p本身的每个数字。这些数字将是2p、3p、4p等；请注意，其中一些可能已经被标记过了。
4）在列表中找到第一个大于p且未标记的数字。如果没有这样的数字，则停止。否则，现在让p等于此数字（即下一个质数），并从步骤3重复。

public static void main(String[] args) {
    int n = 30;
    System.out.printf("Following are the prime numbers below %d\n", n);
    SieveOfEratosthenes(n);
}

static void markMultiples(boolean arr[], int a, int n)
{
    int i = 2, num;
    while ( (num = i*a) <= n )
    {
        arr[ num-1 ] = true; // minus 1 because index starts from 0.
        ++i;
    }
}

// A function to print all prime numbers smaller than n
static void SieveOfEratosthenes(int n)
{
    // There are no prime numbers smaller than 2
    if (n >= 2)
    {
        // Create an array of size n and initialize all elements as 0
        boolean[] arr=new boolean[n];
        for(int index=0;index<arr.length-1;index++){
            arr[index]=false;
        }

        for (int i=1; i<n; ++i)
        {
            if ( arr[i] == false )
            {
                //(i+1) is prime, print it and mark its multiples
                System.out.printf("%d ", i+1);
                markMultiples(arr, i+1, n);
            }
        }
    }
}

Output:-
Following are the prime numbers below 30
2 3 5 7 11 13 17 19 23 29 

- Amit Bhati