PDA

Visualizza la versione completa : [C] ricorsione Fibonacci


SSSS90
18-05-2014, 20:52
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
18-05-2014, 20:58
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.

:ciauz:

SSSS90
18-05-2014, 21:13
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
18-05-2014, 21:18
Prima vengono eseguite le due nuove chiamate e solo dopo la somma dei due risultati viene restituito dalla return

SSSS90
18-05-2014, 21:31
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
18-05-2014, 21:36
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
18-05-2014, 21:44
ok ora ho capito...

oregon
18-05-2014, 21:49
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
18-05-2014, 21:59
grz..ma vorrei un confronto su un altro caso che apro in un altro topic...

Loading