La ricorsione in java

[pierofix]

Qualcuno è così gentile da spiegarmi al volo la ricorsione?

Mille grazie,
Piero.

:ciauz:

[LeleFT]

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]

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]

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]

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]

http://forum.html.it/forum/faccine/021.gif

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

[LeleFT]

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]

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]

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]

Certo..che domande. Era per chi dovesse visitare la pagina in futuro. Meglio lasciare il codice incorretto?