Qualcuno è così gentile da spiegarmi al volo la ricorsione?
Mille grazie,
Piero.
Qualcuno è così gentile da spiegarmi al volo la ricorsione?
Mille grazie,
Piero.
Leading the Web to Its Full Potential...
www.pierofix.it | www.w3.org | www.zeldman.com/externals | http://browsehappy.com | www.alistapart.com | www.webstandards.org | www.flickr.com/photos/pierofix/
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
Vediamo di codificarlo in Java:codice:Fattoriale(0) = 1 Fattoriale (X) = X * Fattoriale(X - 1)
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)codice:int fattoriale(int x) { int risultato = 0; if (x == 0) { // caso base risultato = 1; } else { // caso ricorsivo risultato = x * fattoriale(x-1); } return risultato; }
Vediamolo in Java:codice:Fibonacci(0) = 1 Fibonacci(1) = 1 Fibonacci(X) = Fibonacci(x-1) + Fibonacci(x-2);
Ci sono poi casi di risorsione nella ricorsione... è il caso della funzione di Ackermancodice: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; }
In Java:codice:Ack(0, n) = n + 1 Ack(m+1, 0) = Ack(m, 1) Ack(m+1, n+1) = Ack(m, Ack(m+1, n))
Ciao.codice: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)); } } }
"Perchè spendere anche solo 5 dollari per un S.O., quando posso averne uno gratis e spendere quei 5 dollari per 5 bottiglie di birra?" [Jon "maddog" Hall]
Fatti non foste a viver come bruti, ma per seguir virtute e canoscenza
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.
Leading the Web to Its Full Potential...
www.pierofix.it | www.w3.org | www.zeldman.com/externals | http://browsehappy.com | www.alistapart.com | www.webstandards.org | www.flickr.com/photos/pierofix/
Pronti qua... vediamo di creare una funzione ricorsiva che, presa una stringa, ritorna la stringa inversa (con tutti i caratteri invertiti, esempio "Ciao" --> "oaiC"):
Ciao.codice:public String inverti(String stringa) { return "" + stringa.charAt(stringa.length()-1) + inverti(stringa.substring(0, stringa.length()-1)); }
"Perchè spendere anche solo 5 dollari per un S.O., quando posso averne uno gratis e spendere quei 5 dollari per 5 bottiglie di birra?" [Jon "maddog" Hall]
Fatti non foste a viver come bruti, ma per seguir virtute e canoscenza
Altro esempio... calcoliamo il determinante di una matrice di ordine qualsiasi:
Ciao.codice: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; }
"Perchè spendere anche solo 5 dollari per un S.O., quando posso averne uno gratis e spendere quei 5 dollari per 5 bottiglie di birra?" [Jon "maddog" Hall]
Fatti non foste a viver come bruti, ma per seguir virtute e canoscenza
Velocissimo! Grazie mille di nuovo. Mo stampo... e porto a casa.
Leading the Web to Its Full Potential...
www.pierofix.it | www.w3.org | www.zeldman.com/externals | http://browsehappy.com | www.alistapart.com | www.webstandards.org | www.flickr.com/photos/pierofix/
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.
"Perchè spendere anche solo 5 dollari per un S.O., quando posso averne uno gratis e spendere quei 5 dollari per 5 bottiglie di birra?" [Jon "maddog" Hall]
Fatti non foste a viver come bruti, ma per seguir virtute e canoscenza
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?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 "";
No MP tecnici (non rispondo nemmeno!), usa il forum.
Certo..che domande. Era per chi dovesse visitare la pagina in futuro. Meglio lasciare il codice incorretto?