[ALGORITMO] Funzionamento delle chiamate a funzione ricorsive

[the-bit]

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]

Anche un esempio in C sul fattoriale può andare bene?

[the-bit]

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]

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]

Grazie, sei stato molto chiaro.
Dovrei aver chiarito, finalmente, questa faccenda!

[Hysoka]

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]

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
Ma a prima vista sembra un argomento bello.