Fibonacci e Ricorsione


Riprendiamo in questo post la serie di Fibonacci,
e ne forniamo una formulazione molto elegante, attraverso la ricorsione.

Abbiamo detto che la serie di Fibonacci è ottenuta sommando i due numeri precedenti, a partire dalla coppia 1,1:

1 1 2 3 5 8 13 …

per l’occasione, estendiamo ulteriormente la serie aggiungendo lo zero iniziale,

0 1 1 2 3 5 8 13 …

la tecnica di costruzione della successione, a tutti gli effetti, non cambia, perché si ottiene sempre sommando gli ultimi due numeri. Definiamo una funzione, Fib, sull’insieme dei naturali e verifichiamolo. Le condizioni iniziali diventano:

Fib(0) = 0
Fib(1) = 1

e, da qui, procediamo con la costruzione del prossimo elemento della successione sommando gli ultimi due:

Fib(2) = 0 + 1 = 1

Fib(3) = 1 + 1 = 2

Fib(4) = 2 + 1 = 3

Fib(5) = 3 + 2 = 5

e così via.

Aguzzando la vista si osserva una proprietà piuttosto interessante, sappiamo che  ad ogni passo vengono sommati gli elementi della successione precedenti. Riscriviamo ad esempio Fib(5):

Fib(5) = Fib(3) + Fib(4)

ma sappiamo anche che Fib(3) = Fib(2) + Fib(1) e Fib(4) = Fib(3) + Fib(2), quindi:

Fib(5) = Fib(3) + Fib(4) = Fib(2) + Fib(1)  +   Fib(3) + Fib(2)

e così via.

Riconoscete lo schema ? E’ il tipico esempio di ricorsione: ad ogni passo richiamiamo la funzione Fib aggiungendo elementi costruiti tramite la stessa funzione. La definizione formale, ricorsiva, è:

Fib(0) = 0
Fib(1) = 1

Fib(N) = Fib(N-1) + Fib(N-2)

Per N generico è sufficiente invocare nuovamente la funzione stessa, fino ad arrivare ai due valori iniziali.

La ricorsione fornisce un approccio semplice, potente ed elegante, ma ha un costo: ad ogni passaggio invochiamo nuovamente la funzione facendo crescere il numero di passaggi necessari per calcolarla in modo esponenziale.

Ad esempio, per calcolare Fib(5), occorre calcolare una volta Fib(4), due volte Fib(3), tre volte Fib(2),  quattro volte Fib(1), tre volte Fib(0), per un totale di 14 passi. L’algoritmo (ricordate?) ricorsivo ha, quindi, un costo non indifferente.

La branca della scienza dell’informazione che si occupa del costo di esecuzione di un algoritmo in termini di passi di esecuzione si chiama Teoria della Computabilità e la ricorsione è, per quanto elegante e sintetica, nel novero delle tecniche di approccio alla modellazione di algoritmi, tra quelle meno performanti. In particolare per Fibonacci è possibile scrivere un algoritmo che calcola Fib(5) in modo molto più efficiente, ovvero in soli 5 passi.

Ovviamente, ci torneremo prestissimo.

Annunci
Questa voce è stata pubblicata in Teoria e Pratica e contrassegnata con , , , , , . Contrassegna il permalink.

Una risposta a Fibonacci e Ricorsione

  1. Pingback: Equazioni alle ricorrenze e numeri casuali | LidiMatematici

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...