[l3p] ricorsione (anche teoria generica)

[carra]

Ho dei problemi sulla ricorsione..... e giovedi dopo le vacanze ho la verifica di recupero(devo recuperare un 3).


viruzzino ... aiuta il mio fratellino [ by inno ]

[Zero-2]

L'esempio più semplice per lo studio della ricorsione è quello del fattoriale.

public class Fattoriale{
public static void main(String []Args){
System.out.println("Calcolo del fattoriale");
for(;{
int n=Console.readInt("N>");
System.out.println("IL fattoriale di "+n+ " e' : " +fattoriale(n) );
System.out.println();
}
}
static long fattoriale(int m){
//Il metodo ricorsivo si ferma non appena
// m==0 e comincia a restituire all'istanza che lo ha
//invocato il valore ottenuto , la quale lo restituirà alla
// precedente e così via , fino alla prima istanziazione
// (penso si dica così ) che restituirà il risultato.

if(m==0) return 1;
return m*fattoriale(m-1);
}
}

Ricorsione significa semplicemente richiamare una funzione all'interno della definizione della funzione stessa fino a quando non si verifica una condizione tale che il metodo non sia più ricorsivo , ma cominci il percorso a ritroso , arrivando a fornire il risultato richiesto.Può succedere però che nel percorso a ritroso , ci si ritrovi nella situazione di dover ricominciare la ricorsione .
Si può anche descrivere come un modo che permette di partire da problemi grossi e complessi e piano piano renderli sempre più facili e leggeri fino ad arrivare al punto minimo di semplicità(sempre che esista) e ritornare indietro.
Esistono due tipi di ricorsione , La Ricorsione Diretta e
la Ricorsione Indiretta .
La ricorsione diretta è detta tale quando una funzione richiama se stessa, indiretta quando un funzione richiama un'akltra funzione che a sua volta richiama la prima.
Se tu avessi dovuto calcolare il fattoriale di un numero m, avresti dovuto creare una lista di numeri da 1 a m e poi fare la moltiplicazione. Mentre con la ricorsione risparmi un sacco di righe di codice.
C'è da dire però che la ricorsione consuma molta memoria , perchè istanzia un numero n di volte la stessa classe ed ogni istanziazione resta attiva finchè non viene ritornato il valore richesto alla suceessiva istaza.
Da notare che ogni volta che si fa una invocazione, viene creato un nuovo record di attivazione e le variabili sono diverse.

[bDaniele]

Originariamente inviato da carra
Ho dei problemi sulla ricorsione..... e giovedi dopo le vacanze ho la verifica di recupero(devo recuperare un 3).


viruzzino ... aiuta il mio fratellino [ by inno ]

come già accennato da Zero-2 la ricorsione genera un nuovo stack-frame ad ogni chiamata, quindi il consumo di memoria è notevole, se proprio non sai cosa rispondere, mettila sul piano delle prerformance dicendo che di solito la ricorsione può essere eliminata con un ciclo iterativo (anche se spesso anche quì viene generato uno stack-frame ad ogni passaggio).

[Zero-2]

mettila sul piano delle prerformance dicendo che di solito la ricorsione può essere eliminata con un ciclo iterativo

beh magari guadagni in fatto di performance (anche se non sono molto d'accordo) però ti ammazzi a scrivere codice

Scrivi il metodo di MergeSort con l'iterazione e non con la ricorsione , diventa un pochetto complicato e ingarbugliato , non impossibile intendiamoci

[Michele Facchin]

Immagina (che poi è vero) che la funzione non sappia il risultato da ritornare e continui il suo "ciclo di richiamo a sè stessa" finchè non abbia appunto un valore da ritornare, ti faccio un esempio qui sotto della moltiplicazione col metodo ricorsivo.
Uso il Pascal, che è il linguaggio con cui mi trovo meglio:

function moltiplica(a,b:integer):integer;
 begin
  if (b=0) then
   moltiplica:=0
  else
   moltiplica:=a+moltiplica(a,b-1);
 end;

Analizziamo il codice:

Ho dichiarato una funzione che acquisisce due interi: "a e b" e restituisce un intero che è il prodotto tra questi.

Facciamo un esempio con due numeri: a=5 e b=2.

2 è uguale a 0? No!
quindi faccio:
5+moltiplica(5,2-1) --> 5+moltiplica(5,1) e immagazzino questo risultato che per il momento adesso non sò.

Adesso, 1 è uguale a 0? No!
stesso procedimento
5+moltiplica(5,1-1) --> 5+moltiplica(5,0) e immagazzino questo risultato che per il momento adesso non sò.

Adesso, 0 è uguale a 0? Si!
quindi assegno al ritorno della funzione il valore 0.

Adesso sò il risultato della funzione!!!!
Quindi andando in scala trovo che i valori che prima nn sapevo diventano rispettivamente...
0
5+moltiplica(5,0)=5+0=5
5+moltiplica(5,1)=5+5=10

10 è il valore che ritorna la funzione che se noti è infatti è il prodotto tra 2 e 5

Un pò più chiaro adesso?
La ricorsione immagazina tutti i valori di ritorno finchè non sà un risultato, dopodichè sostituisce il tutto.
PS: Ho usato i colori per farti vedere meglio le sostituzioni.

[bDaniele]

Originariamente inviato da Zero-2
beh magari guadagni in fatto di performance (anche se non sono molto d'accordo) però ti ammazzi a scrivere codice

Scrivi il metodo di MergeSort con l'iterazione e non con la ricorsione , diventa un pochetto complicato e ingarbugliato , non impossibile intendiamoci

Non metto in dubbio la potenza della ricorsione, la mia era solo un'idea da attuare se il prof. ti mette in difficoltà e non sai cosa rispondere!!!!

[Zero-2]

:metallica :metallica :metallica :metallica
:adhone: