La successione consì definita:
   Q(1)=1, Q(2)=1, Q(N+2)=Q(N)+Q(N+1)
illustrata a fianco, nota come successione di Fibonacci, è stata presentata nel "Liber abaci" da Leonardo Pisano (vissuto a cavallo del 1200 e noto come Fibonacci) come modello matematico del seguente "problema dei conigli":
  
 1  1  2  3  5  8  13  …
 ↓  ↓  ↑     ↓  ↓  ↑
  →→→→→→      →→→→→→
              /
alle 8 coppie presenti nel mese precedente si aggiungono le 5 coppie figliate dalle 5 coppie esistenti due mesi prima
«quante coppie di conigli verranno prodotte in N mesi a partire da un'unica coppia se ogni mese ogni coppia dà alla luce una nuova coppia che diventa produttiva a partire dal secondo mese di vita?».
Q(N) rappresenta la quantità di coppie presenti dopo N mesi.  Completa l'elenco dei termini della successione fino a Q(11).  Scrivi un programma (JS o R …) che dando N in input fornisca come output Q(N).

È facile verificare che i valori della successione sino a Q(11) sono 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.
Si può generare la successione facilmente anche con un semplice script (vedi, recursion-C).

I valori sono ottenibili facilmente anche con questa calcolatrice online. Ecco a destra i valori da Q(3) a Q(14) ottenuti nel modo seguente:
   
233 + 144 = 377
89 + 144 = 233
89 + 55 = 144
34 + 55 = 89
34 + 21 = 55
13 + 21 = 34
13 + 8 = 21
5 + 8 = 13
5 + 3 = 8
2 + 3 = 5
2 + 1 = 3
1 + 1 = 2


Posso generare la successione di Fibonacci anche con WolframAlpha.  Vedi qui.


Ecco il calcolo dei valori con R (in R i valori di una variabile indiciata A si ottengono mettendo l'indice tra parentesi quadre invece che tonde, e gli indici partono da 1, non da 0):
## Svuoto Q e le assegno i primi 1000 termini della succ.
Q <- NULL
Q[1] <- 1; Q[2] <- 1; for (i in 3:1000) Q[i] <- Q[i-2]+Q[i-1]
Q[c(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)]
#  1  1  2  3  5  8  13  21  34  55  89 144 233 377 610
## Rappresento graficamente i primi 10 termini
plot(c(0,10),c(0,Q[10]),type="n",xlab="",ylab="")
abline(h=0,v=0,col="blue")
for(i in 1:10) points(i,Q[i]) # ovvero:
n <- 1:10; points(n,Q[n]); lines(n,Q[n])
## Ovvero (se si vuole calcolare un solo output):
F <- function(n) {if(n<3) U <- 1 else {a <- b <- 1;
     for(i in 3:n) {U <- a+b; a <- b; b <- U}}; U}
F(400); Q[400]
# 1.760237e+83 1.760237e+83
## Si poteva anche dare una definizione ricorsiva:
F2 <- function(n) if (n==1 | n==2) 1 else Recall(n-1)+Recall(n-2)
## Le uscite sarebbero state le stesse
F2(10); F(10); Q[10]
# 55  55  55
## ma i tempi sarebbero stati molto più lunghi:
sec <-proc.time()[3]; F2(20); sec2 <- proc.time()[3]-sec; sec2
# 0.09 
sec <-proc.time()[3]; F2(21); sec2 <- proc.time()[3]-sec; sec2
# 0.15 
sec <-proc.time()[3]; F2(22); sec2 <- proc.time()[3]-sec; sec2
# 0.25 
sec <-proc.time()[3]; F2(23); sec2 <- proc.time()[3]-sec; sec2
# 0.4 
sec <-proc.time()[3]; F2(24); sec2 <- proc.time()[3]-sec; sec2
# 0.66 
sec <-proc.time()[3]; F2(25); sec2 <- proc.time()[3]-sec; sec2
# 1.08 
0.15/0.09; 0.25/0.15; 0.4/0.25; 0.66/0.4; 1.08/0.66
# 1.666667 1.666667   1.6       1.65      1.636364
## All'aumento di 1 dell'input il tempo è moltiplicato per circa
## 1.6, ossia il tempo cresce circa come 1.6^n.

Infatti ogni calcolo viene ricondotto ad altri, ciascuno dei quali, se non ha un risultato, viene ricondotto ad altri, e così via. Hanno un andamento simile le uscite: il rapporto tra Q[n] e Q[n-1] tende a stabilizzarsi, e ad assumere il valore 1.6180339887498…. Perchè? Prova a rifletterci. In un esercizio successivo troverai la risposta.

print(c( Q[10]/Q[9],  Q[20]/Q[19],  Q[40]/Q[39],  Q[80]/Q[79] ),15)
# 1.61764705882353 1.61803396316671 1.61803398874989 1.61803398874989