[C] ricorsione Fibonacci

[SSSS90]

Qualcuno saprebbe spiegarmi,con un esempio numerico semplice, ad esempio fibonacci(3) il seguente
algoritmo ricorsivo?

*
Successione di Fibonacci : calcola l ' ultimo valore della successione di
Fibonacci di argomento n
Restituisce il valore calcolato
*/
long fibonacci ( long n) {
/* Casi base */
i f (n == 0 || n == 1)
return n;
else
/* Fasi di divide , impera e combina */
return fibonacci ( n - 1) + fibonacci (n - 2);
}

[minomic]

Ciao,
dal tuo codice, hai che fibonacci(3) = fibonacci(2) + fibonacci(1).
Ma fibonacci(2) = fibonacci(1)+fibonacci(0). <-- ECCO LA RICORSIONE!
Ora sai che fibonacci(0) = 0 e fibonacci(1) = 1.
Quindi
fibonacci(3) = fibonacci(1)+fibonacci(0)+fibonacci(1) = 1+0+1 = 2

In effetti il risultato è corretto, dato che se consideri la successione di Fibonacci 0,1,1,2,3,5,8,13,... hai che il terzo elemento (contando a partire da zero) è proprio 2.

[SSSS90]

grz mille della risposta.Però ancora qualcosina non mi torna:

Obiettivo:Fibonacci(3);->caso base non eseguito->ramo else->return fibonacci(3-1)...ora mi domando ma fibonacci di (n-2)viene eseguito a questo punto del ragionamento o viene solo effettuato return fibonacci(3-1)?spero di essere stato chiaro

come si gestisce la ricorsione doppia delle due funzioni?

[oregon]

Prima vengono eseguite le due nuove chiamate e solo dopo la somma dei due risultati viene restituito dalla return

[SSSS90]

se ho capito bene stai dicendo che contemporaneamente vengono eseguite: fibonacci(3-1) e fibonacci(3-2)?Cerco di spiegarmi meglio ma è davvero difficile:

fibonacci(3-1)->fibonacci(2-1)->ora 1=1 viene eseguito return n che sarebbe :fibonacci(2)*fibonacci(1)=2*1
fibonacci(3-2)->1=1 return n che sarebbe fibonacci(1)=1
a questo punto viene eseguito return fibonacci ( n - 1) + fibonacci (n - 2); ovvero 2+1=3

spero di non aver detto min***te...se è così abbiate pazienza..

[oregon]

Non si capisce bene come scrivi i vari passi ma "contemporaneamente" non viene eseguito nulla.

*Prima* viene fatta la chiamata a fibonacci ( n - 1) e il valore restituito viene memorizzato in una variabile temporanea o in un registro, *subito dopo* viene fatta la chiamata a fibonacci ( n - 2) e il valore restituito viene sommato a quello temporaneo; il risultato viene restituito al chiamante.

[SSSS90]

ok ora ho capito...

[oregon]

In dettaglio, se ti può servire, in codice macchina succede questo

mov         eax,dword ptr [n] 
sub         eax,1 
push        eax  
call        fibonacci (411474h) 
add         esp,4 
mov         esi,eax 

mov         ecx,dword ptr [n] 
sub         ecx,2 
push        ecx  
call        fibonacci (411474h) 
add         esp,4 
add         eax,esi 
...
ret

nella prima parte esegue fibonacci(n-1) e il risultato viene memorizzato temporaneamente in ESI, nella seconda parte viene eseguita fibonacci(n-2) e il risultato in EAX sommato con ESI precedente viene restituito al chiamante tramite la RET.

[SSSS90]

grz..ma vorrei un confronto su un altro caso che apro in un altro topic...