Błąd przepełnienia stosu w rekursji Java

Question

Próbuję zaimplementować kod, który zwraca sumę wszystkich liczb pierwszych poniżej 2 milionów. Mam metodę isPrime (int x), która zwraca wartość true, jeśli liczba jest liczbą pierwszą. Oto ona:

public static boolean isPrime(int x) { 

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

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

     } 
     return true; 

    } 

A druga metoda, która próbuję wdrożyć rekurencyjnie, działa tylko do pewnej liczby, na ten numer i pojawia się błąd przepełnienia stosu. Najwyższy kod dostałem do pracy za 10 000.

Oto ona:

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

Więc dlaczego pojawia się błąd przepełnienia stosu, gdy liczba robi się coraz większy i jak mogę sobie z tym poradzić? Jak zwykle radzisz sobie z pisaniem kodu dla tak dużych liczb? IE: normalne operacje numeryczne takie jak to, ale dla większych liczb? Napisałem to rekursywnie, ponieważ uważałem, że będzie bardziej wydajne, ale nadal nie będzie działać.

Answer 1

Twoja funkcja isPrime jest niewydajna, nie musi iść do x, wystarczy przejść do pierwiastka kwadratowego zx.

Ale to nie jest powód, dla którego Twoje rozwiązanie nie działa. Nie możesz mieć głębokości rekursji 1 miliona.

Rozwiązywałbym ten problem iteracyjnie, używając sieve of eratosthenes i pętli nad wynikową tablicą boolean.

Answer 2

Zastosowanie sit Eratostenesa: -

Poniżej algorytm, aby znaleźć wszystkie liczby pierwsze mniejsze niż lub równe do podanej liczby całkowitej N od Eratostenes sposób:

1) utworzenie listy kolejnych liczb od 2 do n: (2, 3, 4, ..., n).
2) Początkowo niech p równa się 2, pierwsza liczba pierwsza.
3) Począwszy od p, zliczaj przyrosty p i zaznacz każdą z tych liczb większą niż samą na liście. Te liczby to 2p, 3p, 4p itd .; zauważ, że niektóre z nich mogły być już oznaczone.
4) Znajdź pierwszą liczbę większą niż p na liście, która nie jest oznaczona. Jeśli nie było takiej liczby, zatrzymaj się. W przeciwnym razie, niech p teraz równa tej liczby (co jest kolejnym prime) i powtórz czynności od kroku 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

W ogóle, jeśli nadal chcesz użyć rekursji, można użyć rekurencji ogon. W rekurencji każde wywołanie funkcji spowoduje przekazanie pewnych danych do stosu, który jest ograniczony, generując w ten sposób błąd stackoverflow. W rekursji ogonowej nie będziesz naciskał niczego na stos, nie rzucając tym samym wyjątku.

Zasadniczo wystarczy przesłać dane poprzedniego obliczenia jako parametru, zamiast mieć go na stosie.

Więc:

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

z ogona rekursji byłby

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

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

Należy pamiętać, jest to po prostu pseudo kod nie prawdziwy kod Java, ale jest wystarczająco blisko do kodu java.

Aby uzyskać więcej informacji sprawdź

What is tail recursion?