PDA

Visualizza la versione completa : [ALGORITMO] Funzionamento delle chiamate a funzione ricorsive


the-bit
15-12-2010, 19:11
Buona sera,
vorrei capire meglio come effettuano le chiamate a se stesse, le funzioni ricorsive.
Ad esempio, immaginiamo una funziona che calcola l'altezza di un albero binario, ABR, come questa:


// pseudo-codice
Function altezza(tree A)
if eFoglia(A)
then return 0
else
return [1 + max(altezza(SAG), altezza(SAD))] // SAD = sotto albero destro


quello che non ho capito io : esattamente, ogni volta che chiama se stessa, come avviene il procedimento? Cio quali sono i risultati che memorizza?
Diciamo che non riesco a ragionare ancora in termini di "ricorsione".
Se magari poteste farmi degli esempi, tipo su 3 chiamate di questa funzione.

Grazie.

ramy89
16-12-2010, 09:05
Anche un esempio in C sul fattoriale pu andare bene?

the-bit
16-12-2010, 09:46
Si si, l'importante riuscire a capire come avviene ogni chiamata.
Cio come avviene la memorizzazione.
Io ho provato addirittura a farlo su carta...ma proprio non mi ci raccapezzo.

ramy89
16-12-2010, 19:58
Ecco l' esempio del fattoriale in C:



int fattoriale (int a)
{
if(a==1)
return 1;
else
return a*fattoriale(a-1);
}


L' intero principio della funzione ricorsiva si basa sul fatto che prima o poi la funzione smetter di auto-chiamarsi,e questo avviene quando incontra la condizione iniziale (a==1).
Facciamo finta che voglio calcolare il fattoriale di 3,chiamo la funzione:


int x=fattoriale(3);


a diverso da 1,quindi si procede,il ritorno della funzione 3*fattoriale(2);
Ma quant' fattoriale(2)? per calcolarlo bisogna rieseguire la funzione fattoriale.
a diverso da 1,quindi il ritorno 2*fattoriale(1),il ritorno totale per ora 3*2*fattoriale(1).
Adesso la funzione viene rieseguita di nuovo.
stavolta a uguale a 1,quindi il ritorno 1.
Il ritorno totale 3*2*1 =6.

the-bit
16-12-2010, 23:16
Grazie, sei stato molto chiaro.
Dovrei aver chiarito, finalmente, questa faccenda!
:ciauz:

Hysoka
17-12-2010, 21:44
la ricorsione pu essere vista come il principio di induzione.
in pratica devi scindere dal caso base e dal "passo induttivo".
La cosa molto importante, se vuoi veramente padroneggiare la ricorsione, che tutte le operazioni vengono eseguite alla rovescia di come tu possa realmente pensare. Riprendendo il fattoriale di 3, la macchina (ma anche l'uomo deve) deve prima calcolarsi il fattoriale di 2. E' come lo fa? Chiamando se stessa fino ad arrivare al caso base.
Spesso si usa (o se non addirittura sempre) si usa la ricorsione per determinare soluzioni a problemi dello stesso tipo.
Infatti, un albero binario non altro un nodo con due figli che, a loro volta (possono) hanno due figli e, quindi, sono anch'essi degli alberi binari.
Spero d non averti fatto confondere di pi.

ramy89
17-12-2010, 22:37
Infatti nei naturali se dimostri che un' equazione valida per n=1,e che se valida per n anche valida per n+1,hai dimostrato che questa equazione valida per tutto n.Quoto che stiamo usando il principio di induzione.


Originariamente inviato da Hysoka
Infatti, un albero binario non altro un nodo con due figli che, a loro volta (possono) hanno due figli e, quindi, sono anch'essi degli alberi binari.
Spero di non averti fatto confondere di pi.

Con questo hai confuso anche me,devo ancora farli gli alberi :zizi:
Ma a prima vista sembra un argomento bello.

Loading