Ошибка переполнения стека в рекурсии Java

Question

Я пытаюсь реализовать код, который возвращает сумму всех простых чисел менее 2 миллионов. У меня есть метод 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; 
} 

Так почему я получаю ошибку переполнения стека, когда число становится больше, и как я могу справиться с этим? Кроме того, как вы обычно разбираетесь в написании кода для таких больших чисел? IE: нормальное число операций, подобных этому, но для больших чисел? Я написал это рекурсивно, потому что я думал, что он будет более эффективным, но он все равно не будет работать.

Answer 1

Ваша функция isPrime неэффективна, ей не нужно идти в x, достаточно пройти квадратный корень от x.

Но это не причина, по которой ваше решение не работает. У вас не может быть рекурсии глубиной 1 миллион.

Я бы решил эту проблему итеративно, используя sieve of eratosthenes и за цикл по полученному массиву boolean.

Answer 2

Использование решето Эратосфена: -

Ниже приводится алгоритм нахождения всех простых чисел меньше или равно заданному числа п по методу Эратосфена:

1) Создать список последовательных целых чисел от 2 до n: (2, 3, 4, ..., n).
2) Первоначально пусть p равно 2, первое простое число.
3) Начиная с p, подсчитывайте с шагом p и отмечайте каждое из этих чисел больше, чем p в списке. Эти цифры будут 2p, 3p, 4p и т. Д .; обратите внимание, что некоторые из них, возможно, уже отмечены.
4) Найдите первое число, большее, чем 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 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?