fibonacci e ricorsione

[Jupiter]

ciao


volevo chiedere chiarimenti sulla formula sottoindicata

fibonacci(i-1) + fibonacci(i-2);

è inerente ad uno script che mostra il valore di Fibonacci ad una data
posizione...es inserisci 7 e ti stampa

"al 7° posto della serie Fibonacci vi è il 13" infatti 0 - 1 - 2 - 3 -
5 - 8 - 13

il punto pero' è che volevo capire di piu' su cosa fa esattamente
fibonacci(i-1) + fibonacci(i-2);

se inserisco 7

otterro'

fibonacci(6) + fibonacci(5);

quindi la chiamata fibonacci(6) -> fibonacci(5) + fibonacci(4);
mentre quindi la chiamata fibonacci(5) -> fibonacci(4) + fibonacci(3);

etc...?

vorrei insomma capire come esce 13 se appunto inserisco 7


grazie

[Luigi Rosa]

Post by Jupiter
vorrei insomma capire come esce 13 se appunto inserisco 7

Perche' 5 (AKA fibonacci(5)) piu' 8 (AKA fibonacci(6)) fa 13.

Nella formula per ricorssione di Fibonacci restituisci fibonacci(i-1) +
fibonacci(i-2) per i>3 altrimenti restituisci dei valori fissi (0 e 1)
altrimenti la ricorsione non ha termine.


Occhio che le funzioni ricorsive hanno il brutto vizio di occupare TANTA memoria :)



Ciao,
luigi

[Cujo]

Post by Jupiter
se inserisco 7
otterro'
fibonacci(6) + fibonacci(5);
quindi la chiamata fibonacci(6) -> fibonacci(5) + fibonacci(4);
mentre quindi la chiamata fibonacci(5) -> fibonacci(4) + fibonacci(3);
etc...?

Si, finchè arrivi ad uno dei due casi "base" cui è assegnato un valore
per *definizione*, ovvero nel tuo caso

fib(0) = 1
fib(1) = 1

Post by Jupiter
vorrei insomma capire come esce 13 se appunto inserisco 7

Andando avanti col ragionamento che stavi portando avanti sopra,
arriveresti ad una somma di (tanti) termini che valgono fib(0) oppure
fib(1), ovvero 1. Il tredici verrà fuori da 1+1+1+1+1+1+1+1+1+1+1+1+1.

Cmq. ti consiglio di usare un esempio più semplice per comprendere la
ricorsione.

Un esempio più adeguato IMHO è il fattoriale, quando hai ben capito
questo ri-considera fibonacci.

Googola un po', es:

<http://lia.deis.unibo.it/Courses/FondA-INF/lucidi/10-ricorsione.PDF>

Tieni presente che qualsiasi algoritmo ricorsivo può essere riscritto in
modo iterativo e che un algoritmo iterativo equivalente può essere
*molto* più efficiente (in termini di memoria soprattutto, ma anche di
tempi (overhead)) dell'equivalente ricorsivo.

Per contro la ricorsione è didatticamente figa e terribilmente elegante
(IMHO). Ha un certo fascino.

ciao, f.

[Luigi Rosa]

Post by Cujo
Per contro la ricorsione è didatticamente figa e terribilmente elegante
(IMHO). Ha un certo fascino.

Si dice, infatti, "to iterate is human, to recurse is divine" :)


Ciao,
luigi

[Cujo]

Post by Luigi Rosa
Si dice, infatti, "to iterate is human, to recurse is divine" :)

... and only Chuck Norris can recurse without a base case.

;)

ciao, f.

[Redwiz]

Post by Cujo
<http://lia.deis.unibo.it/Courses/FondA-INF/lucidi/10-ricorsione.PDF>
Tieni presente che qualsiasi algoritmo ricorsivo può essere riscritto in
modo iterativo e che un algoritmo iterativo equivalente può essere
*molto* più efficiente (in termini di memoria soprattutto, ma anche di
tempi (overhead)) dell'equivalente ricorsivo.

Programma Ricorsivo: "Ehi, dove diamine è finito lo stack!?!?! "
Programma Iterativo: "È al cesso, gli hai fatto fare indigestione"

:-)

[Luigi Rosa]

Post by Redwiz
Programma Ricorsivo: "Ehi, dove diamine è finito lo stack!?!?! "
Programma Iterativo: "È al cesso, gli hai fatto fare indigestione"
:-)

LOL! Del resto lo stack e' li per essere usato, non per tenerlo sempre
inutilmente vuoto!



Ciao,
luigi