Java递归中的堆栈溢出错误

Question

我正在尝试实现一个返回所有素数总和小于200万的代码。我有一个isPrime（intx）方法，如果数字是素数，它将返回true。这是：

public static boolean isPrime(int x) {

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

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

        }
        return true;

    }

而另一种方法，我尝试递归实现，只在某个数字之前有效，超过这个数字，我得到一个堆栈溢出错误。我得到的最高代码是10000美元

这是：

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;
}

那么，当数字变大时，为什么会出现堆栈溢出错误？我该如何处理？ 另外，您通常如何处理为如此大的数字编写代码的问题？IE：像这样的正常数字运算，但对于较大的数字？我递归地写了这篇文章，因为我认为它会更有效，但它仍然不起作用

Answer 1

使用Eratosthenes筛：

下面是通过Eratosthenes方法找到所有小于或等于给定整数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 

Answer 2

你的isPrime函数效率很低，它不必去x，去x的平方根就足够了

但这并不是你的解决方案不起作用的原因。递归深度不能为100万

我将迭代地解决这个问题，在生成的boolean数组上使用sieve of eratosthenes和for循环

Answer 3

一般来说，如果仍然想使用递归，可以使用尾部递归。 在递归中，每个函数调用都会将一些数据推送到堆栈中，这是有限的，因此会产生stackoverflow错误。在尾部递归中，不会将任何内容推送到堆栈中，因此不会抛出异常

基本上，您只需要将上一次计算的数据作为参数发送，而不是将其放在堆栈上

所以：

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代码非常接近

欲了解更多信息，请查看

What is tail recursion?