Corrigé
Récursif
En notant $A(n)$ le nombre d'appels à la fonction, on a :
- l'appel proprement dit,
- le nombre d'appel à
fibonacci_rec(n-1)
- le nombre d'appel à
fibonacci_rec(n-2)
Ce qui donne l'équation suivante :
En notant $C(n)$ la complexité de la fonction, on a l'équation de récurrence suivante :
La complexité étant croissante, on a que : $C(n-1) \geq C(n-2)$ et on a bien l'inégalité :
On peut reappliquer l'inégalité de récurrence autant de fois que l'on veut ce qui donne, en l'appliquant $K$ fois :
Les seules valeurs de $C(n)$ connues sont celles pour $n=1$ ou $n=2$. Il faut donc appliquer notre formule pour $K=n-2$, ce qui donne l'inégalité :
De même, en utilisant l'inégalité $\mathcal{O}(1) + 2 \cdot C(n-2) \leq C(n)$, on obtient :
De même que précédemment, en applicant l'inégalité de récurrence $K$ fois :
Les seules valeurs de $C(n)$ connues sont celles pour $n=1$ ou $n=2$. Il faut donc appliquer notre formule pour $K=\frac{n-2}{2}$, ce qui donne l'inégalité :
La fin est facile en utilisant le fait que $\sum_{i=0}^{K}2^i = 2^{K+1} - 1$
Valeur de $F(n)$
On prouve la propriété par récurrence.
Initialisation :
- $F(1) = 1 = \frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2} - \frac{1-\sqrt{5}}{2}) = \frac{1}{\sqrt{5}}(\varphi - \frac{1}{-\varphi})$
- $F(2) = \frac{1}{\sqrt{5}}(\varphi^2-\frac{1}{(-\varphi)^2}) = \frac{1}{\sqrt{5}}(\varphi + 1 -(\frac{1}{(-\varphi)} + 1) = \frac{1}{\sqrt{5}}(\varphi + \frac{1}{\varphi}) = F(1)$
On suppose la propriété vrai jusqu'à $n-1$. Pour $n$ :
$F(n) = F(n-1) + F(n-2) = \frac{1}{\sqrt{5}}(\varphi^{n-1}-\frac{1}{(-\varphi)^{n-1}}) + \frac{1}{\sqrt{5}}(\varphi^{n-2}-\frac{1}{(-\varphi)^{n-2}}) = \frac{1}{\sqrt{5}}(\varphi^{n-2}(1 + \varphi) - \frac{1}{(-\varphi)^{n-2}}(1+ \frac{1}{\varphi}))$
Comme $\varphi$ et $-\frac{1}{\varphi}$ sont les racines du polynôme $P(X) = X^2 - X -1$ on a :
$F(n) = \frac{1}{\sqrt{5}}(\varphi^{n-2}(\varphi^2) - \frac{1}{(-\varphi)^{n-2}}(\frac{1}{\varphi^2})) = \frac{1}{\sqrt{5}}(\varphi^n-\frac{1}{(-\varphi)^n})$
Itératif
def fibo_iter(n):
a = 1
b = 1
for i in rang(n):
a, b = a+b, a
return a
Récursif terminal
La complexité étant terminale, il y a $\mathcal{O}(n)$ appels récursifs. Comme le reste de la fonction est en $\mathcal{O}(1)$ la complexité totale est en $\mathcal{O}(n)$.
Le fait que la fonction calcule bien la suite de Fibonacci se fait par récurrence. On va montrer par récurrence que fibo_rec2(n, a, b)
rend la valeur de la suite pour $F(1) = b$ et $F(2) = a$.
- Initialisation :
fibo_rec2(1, a, b) = b
etfibo_rec2(2, a, b) = a
- On suppose la propriété vraie pour
fibo_rec2(n-1, a, b)
. Commefibo_rec2(n, a, b) = fibo_rec2(n-1,a+b , a)
, la propriété est vérifiée.