PDA

Visualizza la versione completa : La ricorsione in java


 
pierofix
07-12-2004, 15:44
Qualcuno è così gentile da spiegarmi al volo la ricorsione?

Mille grazie,
Piero.

:ciauz:

LeleFT
07-12-2004, 15:59
La Ricorsione si attua quando una funzione richiama se stessa per produrre il risultato. La chiamata avviene passando dei parametri "più semplici", in modo da raggiungere il caso base, che rappresenta il caso più semplice in assoluto.

Facciamo un esempio classico, il calcolo del fattoriale: in matematica il fattoriale è definito ricorsivamente come segue


Fattoriale(0) = 1
Fattoriale (X) = X * Fattoriale(X - 1)

Vediamo di codificarlo in Java:


int fattoriale(int x) {
int risultato = 0;
if (x == 0) { // caso base
risultato = 1;
} else { // caso ricorsivo
risultato = x * fattoriale(x-1);
}
return risultato;
}

La ricorsione, però, può non essere sempre singola... può capitare il caso di una doppia ricorsione. E' il caso del calcolo della serie di fibonacci, definita come segue (in una delle 2 varianti)


Fibonacci(0) = 1
Fibonacci(1) = 1
Fibonacci(X) = Fibonacci(x-1) + Fibonacci(x-2);

Vediamolo in Java:


int fibonacci(int x) {
int risultato = 0;
if ((x == 0) || (x == 1)) { // casi base
risultato = 1;
} else { // caso ricorsivo
risultato = fibonacci(x-1) + fibonacci(x-2);
}
return risultato;
}

Ci sono poi casi di risorsione nella ricorsione... è il caso della funzione di Ackerman


Ack(0, n) = n + 1
Ack(m+1, 0) = Ack(m, 1)
Ack(m+1, n+1) = Ack(m, Ack(m+1, n))

In Java:


int Ack(int x, int y) {
int risultato = 0;
if (x == 0) { // caso base
risultato = y + 1;
} else {
if (y == 0) { // 1° caso ricorsivo
risultato = Ack(x-1, 1);
} else { // 2° caso ricorsivo
risultato = Ack(x-1, Ack(x, y-1));
}
}
}

Ciao. :ciauz:

pierofix
07-12-2004, 16:03
Grazie capitano! http://forum.html.it/forum/faccine/026.gif

Sei stato molto chiaro, peccato che sono gli stessi identici esempi che ho io sul libro... :cry:
Cercavo qualcosa di diverso, comunque grazie mille davvero.


:ciauz:

LeleFT
07-12-2004, 16:09
Pronti qua... vediamo di creare una funzione ricorsiva che, presa una stringa, ritorna la stringa inversa (con tutti i caratteri invertiti, esempio "Ciao" --> "oaiC"):


public String inverti(String stringa) {
return "" + stringa.charAt(stringa.length()-1) +
inverti(stringa.substring(0, stringa.length()-1));
}


Ciao. :ciauz:

LeleFT
07-12-2004, 16:16
Altro esempio... calcoliamo il determinante di una matrice di ordine qualsiasi:


public long det (int [][] matrice, int ordine) {
long risultato = 0;
int [][] nuova;
int pos;

if (ordine == 2)
risultato = matrice[0][0] * matrice[1][1] - matrice[0][1] * matrice[1][0];
else {
nuova = new int[ordine-1][ordine-1];
for (int k=0; k<ordine;k++) {
for (int i=1; i<ordine; i++) {
pos = 0;
for (int j=0; j<ordine; j++)
if (j != k) {
nuova[i-1][pos] = matrice[i][j];
pos++;
}
}

if ((k % 2) == 0)
risultato = risultato + matrice[0][k] * det(nuova, (ordine-1));
else
risultato = risultato - matrice[0][k] * det(nuova, (ordine-1));
}
}

return risultato;
}

Ciao. :ciauz:

pierofix
07-12-2004, 16:16
http://forum.html.it/forum/faccine/021.gif

Velocissimo! Grazie mille di nuovo. Mo stampo... e porto a casa. :ciauz:

LeleFT
07-12-2004, 16:18
Prova ad inventartene qualcuna anche tu... anche di stupidaggini, come calcolare la somma di tutti i valori contenuti in nu array in modo ricorsivo...


Ciao. :ciauz:

mr87
01-03-2009, 17:19
Il metodo per l'inversione della stringa è errato...manca il caso base :dottò: un fondamento della programmazione ricorsiva.
Va aggiunto if(stringa.length()==0)return "";

oregon
01-03-2009, 17:25
Originariamente inviato da mr87
Il metodo per l'inversione della stringa è errato...manca il caso base :dottò: un fondamento della programmazione ricorsiva.
Va aggiunto if(stringa.length()==0)return "";

E' un thread del 2004 !!! L'hai visto?

mr87
01-03-2009, 20:55
Certo..che domande. Era per chi dovesse visitare la pagina in futuro. Meglio lasciare il codice incorretto?

Loading