Definizione ricorsiva dei numeri di Fibonacci

• $F(0)=0$
• $F(1)=1$
• $F(n) =F(n-1)+F(n-2)$ per $n \geq 2$

Pseudocodice

procedure Fibonacci(n)
	if n = 0 then
		return 0
	else if n = 1 then
		return 1
	else
		return Fibonacci(n-1)+Fibonacci(n-2)

Dimostrazione

Proviamo la correttezza dell’algoritmo descritto da $Fibonacci(n)$, dimostriamo cioè che il valore restituito dalla procedura $Fibonacci(n)$ coincide con $F(n)$

dim: per induzione forte su $n \geq 0$

• base:

  • se $n = 0$, il primo passo dell’algoritmo restituisce il valore $0$ , ed è corretto perchè $F(0)=0$
  • se $n= 1$, il secondo passo dell’algoritmo restituisce il valore $1$, ed è corretto perchè $F(1)=1$

• passo di induzione:

  ipotesi induttiva: $Fibonacci(k)$ computa correttamente per tutti i valori $k \leq n$ con $n,k \in \mathbb N$, cioè restituisce $F(k)$

  Ora mostriamo che $Fibonacci(n+1)$ computa correttamente anche $F(n+1)$:

  La procedura $Fibonacci(n+1)$ restituisce $Fibonacci(n)+Fibonacci(n-1)$

  Per ipotesi induttiva sappiamo che $Fibonacci(n)=F(n)$ e $Fibonacci(n-1)=F(n-1)$

  Quindi otteniamo che $Fibonacci(n+1) = Fibonacci(n)+Fibonacci(n-1)=F(n)+F(n-1)=F(n+1)$

Pertanto l’algoritmo $Fibonacci(n)$ computa correttamente $\forall n \geq 0$