Errore di overflow dello stack nella ricorsione Java

Question

Sto tentando di implementare un codice che restituisce la somma di tutti i numeri primi inferiori a 2 milioni. Ho un metodo isPrime (int x) che restituisce true se il numero è primo. Eccolo:

public static boolean isPrime(int x) { 

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

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

     } 
     return true; 

    } 

E l'altro metodo, che sto cercando di implementare in modo ricorsivo, funziona solo fino ad un certo numero, più di quel numero e ottengo un errore di overflow dello stack. Il massimo che ho ottenuto è che il codice funzionasse per 10.000.

Eccolo:

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

Allora perché ottengo un errore di overflow dello stack quando il numero diventa più grande e come posso fare con questo? Inoltre, come si fa normalmente a scrivere codice per numeri così grandi? IE: operazioni con numeri normali come questo, ma per numeri più grandi? Ho scritto questo in modo ricorsivo perché pensavo che sarebbe stato più efficiente ma non funzionerebbe ancora.

Answer 1

La tua funzione isPrime è inefficiente, non è necessario andare a x, è sufficiente passare alla radice quadrata di x.

Ma questo non è il motivo per cui la soluzione non funziona. Non puoi avere una profondità di ricorsione di 1 milione.

Vorrei risolvere questo problema in modo iterativo, utilizzando sieve of eratosthenes e il ciclo sull'array boolean risultante.

Answer 2

Uso crivello di Eratostene: -

seguito è l'algoritmo di trovare tutti i numeri primi minori o uguali a un dato intero n con il metodo di Eratostene:

1) Creare un elenco di numeri interi consecutivi da 2 a n: (2, 3, 4, ..., n).
2) Inizialmente, sia p uguale a 2, il primo numero primo.
3) A partire da p, contare fino a incrementi di p e contrassegnare ciascuno di questi numeri maggiore di p stesso nell'elenco. Questi numeri saranno 2p, 3p, 4p, ecc .; si noti che alcuni di essi potrebbero essere già stati contrassegnati.
4) Trova il primo numero maggiore di p nell'elenco che non è segnato. Se non c'era un tale numero, fermati. In caso contrario, lasciare che p ora uguale a questo numero (che è il prossimo primo), e ripetere dal passaggio 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

In generale, se si desidera comunque utilizzare la ricorsione, è possibile utilizzare la ricorsione in coda. Nella ricorsione ogni chiamata di funzione spinge alcuni dati nello stack, che è limitato, generando così un errore di stackoverflow. Nella ricorsione di coda non spingerai nulla in pila, quindi non farai eccezione.

In pratica tutto ciò che serve è inviare i dati del calcolo precedente come parametro invece di averlo in pila.

Quindi:

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

con la coda ricorsione sarebbe

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

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

Tenete a mente questo è solo pseudo non codice java reale, ma è abbastanza vicino al codice Java.

Per maggiori informazioni controllare

What is tail recursion?