La ricorsione in java

[pierofix]

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

Mille grazie,
Piero.

[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.

[pierofix]

Grazie capitano!

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

[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.

[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.

[pierofix]

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

[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.

[mr87]

Il metodo per l'inversione della stringa è errato...manca il caso base 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 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?