Re: [Java, Algoritmi] StackOverflowError (ordinamento-sorting)

Messaggioda claudio86 » 09/09/2018, 21:08

Innanzitutto: in una sola riga 1) confronti due valori, 2) modifichi una variabile, 3) chiami ricorsivamente la funzione e 4) restituisci un valore. Sono tutte operazioni separate, mettile su righe separate. In generale, dopo un punto e virgola vai sempre a capo, la leggibilità è importante.


Il problema è che chiami la tua funzione ricorsivamente N volte. Ogni volta che chiami la funzione viene consumata memoria sullo stack (almeno l'indirizzo di ritorno, più tutte le variabili locali). Se N è troppo grande lo stack non può contenere tutte le funzioni.

Hai due alternative:
- Riscrivere la funzione in modo che sia tail-recursive
- Riscrivere la funzione in modo iterativo (che è concettualmente la stessa cosa, una funzione tail-recursive è implementabile tramite iterazione)

Una funzione è tail-recursive se, ogni volta che chiama se stessa ricorsivamente, è l'ultima istruzione che esegue. La tua funzione non lo è: dopo aver chiamato se stessa deve usare il risultato nell'espressione da restituire. Quella funzione causerà uno stack overflow in qualsiasi linguaggio, non è un problema di Java.

La procedura standard per trasformare una funzione ricorsiva in una funzione tail-recursive è di usare un accumulatore. L'esempio classico del fattoriale:

Codice:
int factorial(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

int factorial_tail_recursive_inner(int n, int accumulator) {
    if (n == 0) {
        return accumulator;
    } else {
        int new_accumulator = n * accumulator;
        return factorial_tail_recursive_inner(n - 1, new_accumulator);
    }
}

int factorial_tail_recursive(int n) {
    int initial_accumulator = 1;
    return factorial_tail_recursive_inner(n, initial_accumulator);
}

int factorial_iterative(int n) {
    int accumulator = 1; // initial_accumulator
    for (int i = 0; i < n; ++i) {
        accumulator = n * accumulator; // recursive step
    }
    return accumulator;
}


Come vedi, in factorial_tail_recursive_inner() quando chiami ricorsivamente la funzione non hai più altre operazioni, restituisci direttamente il risultato. Questo permette al programma di liberare lo spazio prima della chiamata, dato che non servono più informazioni sulla funzione chiamante, quindi lo stack non cresce (semplificando molto).
Invece di usare il valore restituito dalla ricorsione mantieni un accumulatore continuamente aggiornato che viene passato lungo la ricorsione. Come vedi la soluzione iterativa è praticamente identica a quella tail-recursive. Si tratta esattamente di un ciclo implementato tramite ricorsione.

Quindi devi trovare un modo di riscrivere la tua funzione in modo che usi un accumulatore.
"This theorem, as many others, is proven by writing zero in a creative way…"
claudio86
Senior Member
Senior Member
 
Messaggio: 497 di 1130
Iscritto il: 09/01/2011, 15:12

Re: [Java, Algoritmi] StackOverflowError (ordinamento-sorting)

Messaggioda curie88 » 11/09/2018, 07:13

Ciao @claudio86,

Ho dovuto aggirare la ricorsione con un codice iterativo, per il calcolo della radice quadrata d' esempio, perché non ne venivo a capo; posto il codice e lascio a voi interventi migliorativi:

Codice:

    private static double sqrtX(double x, double sqX){
        //restituisce il valore approssimato della radice di x in funzione di x
        //e della sua radice approssimata sqX
        x = 1+(x-1)/(1+sqX);
        return x;
    }

    private static double sqrt(double x, int n_cifre){
        double Sq=sqrt2(x,0);
        if (Sq*Sq==x) return Sq;
        else return sqrt2(x,n_cifre);
    }
   
    private static double sqrt2(double x,int n_cifre){       
                                                                   
            //ottiene la lunghezza della radice quadrata di x:
            int lngRadInt=Integer.toString((int)x).length();
           
            if (lngRadInt>1) lngRadInt/=2;
                       
            double Sq=sqrtX(x,x);  //calcola il primo valore approssimato della radice           
           
            double apx = Math.pow(10,-n_cifre);
           
            double S=Sq;           
             
            Sq=sqrtX(x,Sq); //calcola il secondo valore approssimato della radice
                                   
            double Q=Sq*Sq;  //esegue il quadrato della radice         

            double diff=Math.abs(Sq-S);
           
            //Ricalcola la radice fino all' approssimazione apx opportuna:
            while (Q!=x && diff>apx){
                 S=Sq;
                 Sq=sqrtX(x,Sq);
                     Q=Sq*Sq;
                     diff=Math.abs(Sq-S);                     
            }
           
            //Tronca il numero alla cifra significativa opportuna:
            String str = Double.toString(Sq).substring(0, n_cifre+lngRadInt+1);
                   Sq = Double.parseDouble(str);
                   
            return Sq;  //restituisce il valore della radice quadrata di x                 
               
    }
   



Come vedete, ho ulteriormente aggiornato il codice, ora funziona anche per valori non interi di $x$ e l' esecuzione non è più lenta per valori grandi di $x$. Accetto comunque critiche se migliorano ulterriormente il programma.

Buona giornata e grazie.
“Tutte le scienze esatte sono dominate dall'idea dell'approssimazione.” Bertrand Russell.
curie88
Senior Member
Senior Member
 
Messaggio: 412 di 1070
Iscritto il: 21/07/2015, 15:44

Precedente

Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite