def fibonacci(n) :
    if n <= 1 : return 1
    else : return fibonacci(n-1)+fibonacci(n-2)
        
        
print([fibonacci(n) for n in range(10)])

Le début d'arbre des appels pour fibonacci(8) :

Un traceur python :

def tracer(f):
	decalage = 0
	def g(x):
		nonlocal decalage
		print('|        ' * decalage, end='')
		print('|Appel {}({})'.format(f.__name__,x))
		decalage +=1
		imagefx = f(x)
		print('|        ' * decalage, end='')
		print('|-> retourne {}'.format(imagefx) )
		decalage -= 1
		return imagefx
	return g	
	
# on peut utiliser le décorateur : @tracer
# ou écrire ci-dessous la ligne fibonacci = tracer(fibonacci)
def fibonacci(n):
	if n <= 1 : return 1
	else : return fibonacci(n-1) + fibonacci(n-2)
 
 
fibonacci = tracer(fibonacci)
 
fibonacci(6)

On obtient :

|Appel fibonacci(6)
|        |Appel fibonacci(5)
|        |        |Appel fibonacci(4)
|        |        |        |Appel fibonacci(3)
|        |        |        |        |Appel fibonacci(2)
|        |        |        |        |        |Appel fibonacci(1)
|        |        |        |        |        |        |-> retourne 1
|        |        |        |        |        |Appel fibonacci(0)
|        |        |        |        |        |        |-> retourne 1
|        |        |        |        |        |-> retourne 2
|        |        |        |        |Appel fibonacci(1)
|        |        |        |        |        |-> retourne 1
|        |        |        |        |-> retourne 3
|        |        |        |Appel fibonacci(2)
|        |        |        |        |Appel fibonacci(1)
|        |        |        |        |        |-> retourne 1
|        |        |        |        |Appel fibonacci(0)
|        |        |        |        |        |-> retourne 1
|        |        |        |        |-> retourne 2
|        |        |        |-> retourne 5
|        |        |Appel fibonacci(3)
|        |        |        |Appel fibonacci(2)
|        |        |        |        |Appel fibonacci(1)
|        |        |        |        |        |-> retourne 1
|        |        |        |        |Appel fibonacci(0)
|        |        |        |        |        |-> retourne 1
|        |        |        |        |-> retourne 2
|        |        |        |Appel fibonacci(1)
|        |        |        |        |-> retourne 1
|        |        |        |-> retourne 3
|        |        |-> retourne 8
|        |Appel fibonacci(4)
|        |        |Appel fibonacci(3)
|        |        |        |Appel fibonacci(2)
|        |        |        |        |Appel fibonacci(1)
|        |        |        |        |        |-> retourne 1
|        |        |        |        |Appel fibonacci(0)
|        |        |        |        |        |-> retourne 1
|        |        |        |        |-> retourne 2
|        |        |        |Appel fibonacci(1)
|        |        |        |        |-> retourne 1
|        |        |        |-> retourne 3
|        |        |Appel fibonacci(2)
|        |        |        |Appel fibonacci(1)
|        |        |        |        |-> retourne 1
|        |        |        |Appel fibonacci(0)
|        |        |        |        |-> retourne 1
|        |        |        |-> retourne 2
|        |        |-> retourne 5
|        |-> retourne 13

Dans les deux cas, on voit que certains calculs sont lancés à plusieurs reprises, d'où l'inefficacité de ce script.

On constate que les temps de calcul deviennent rapidement excessifs. Essayer par exemple de calculer fibonacci(50) avec ce script : on irait plus vite en calculant à la main !

Notons \( a_n \) le nombre d'additions dans l'évaluation de fibonacci(n).

On a : \( a_0 = 0 \), \( a_1= 0 \) et pour \( n \geqslant 2 \) : \( a_n = a_{n-1}+a_{n-2}+1 \).

En posant \( f_n = a_n +1 \), on voit que\( f_n = f_{n-1} +f_{n-2}\) avec \( f_0 = f_1 =1\).

On rappelle que \( f_n = \frac{1}{\sqrt{5}} \times \left( \phi^{n+1} - \left(\frac{1-\sqrt{5}}{2}\right)^{n+1} \right) \) où \( \phi = \frac{1+\sqrt{5}}{2} \) (démonstration par récurrence par exemple).

On a \( a_n \approx -1 + \frac{1}{\sqrt{5}} \times \phi^{n+1} \) pour n ≥ 4.

On a donc un nombre d'additions qui croît de façon exponentielle, ce qui explique des temps très rapidement non raisonnables pour un calcul aussi simple.

Le nombre d'additions pour fibonacci(50) est environ \( a_{50} \approx -1 + \frac{1}{\sqrt{5}} \times \phi^{51} \), soit \( a_{50} \approx 32\, 951\, 280\, 099\).

Estimation du temps de calcul de fibonacci(50) sur machine :

from timeit import timeit

def addition(a,b) :
	return a+b


repet = 10**7
tps = timeit(stmt='addition(2000062600,3452628998929)',setup="from __main__ import addition",number=repet)
tpsmoyen = tps/repet
print("temps addition ", tpsmoyen)

print("Estimation du temps de calcul de fibonacci(50) en heures : ",  tpsmoyen * 32951280099 / (60*60) )

# et pour F(500) : 
nbAdd = 5**(-0.5) * (0.5 * (1+5**0.5))**501
print("Estimation du temps de calcul de fibonacci(500) en années : ",  tpsmoyen * nbAdd / (60*60*24*365.25) )

Sur ma machine :

temps addition  1.824835774001258e-07
Estimation du temps de calcul de fibonacci(50) en heures :  1.6702965201053033
Estimation du temps de calcul de fibonacci(500) en années :  1.3044954907961674e+90

Remarque : pour bien comprendre les 10⁹⁰ années, rappelons que l'âge de l'univers est estimé à 14 × 10⁹ années... Ca vous laisse le temps d'aller prendre un café.

On estime le temps de calcul de fibonacci(20) puis on évalue celui de fibonacci(50) en multipliant par \( \phi^{50-20}\) et celui de fibonacci(500) en multipliant par \( \phi^{500-20}\)

from timeit import timeit
from math import sqrt

def fibonacci(n) :
    if n <= 1 : return 1
    else : return fibonacci(n-1)+fibonacci(n-2)
    
    
phi =  1/2 * (1 + sqrt(5)) 


# temps en seconde pour repet répétitions du calcul de fibonacci(20) :
repet = 1000
tps = timeit(stmt='fibonacci(20)',setup="from __main__ import fibonacci",number=repet)
tps20 = tps/repet
print("temps fibonacci(20) : ", tps20)

print("Estimation du temps de calcul de fibonacci(50) en heures : ",  tps20 * phi**30 / (60*60) )
print("Estimation du temps de calcul de fibonacci(500) en années : ",  tps20 * phi**480 / (60*60*24*365.25) ) 

Sur ma machine :

temps fibonacci(20) :  0.003803203324001515
Estimation du temps de calcul de fibonacci(50) en heures :  1.9655144938600373
Estimation du temps de calcul de fibonacci(500) en années :  2.4837786911572107e+90

def fibonacci(n, a=1, b=1):
    if n==0 : return a
    elif n==1 : return b
    else : return fibonacci(n-1, b, a+b)
 
 
for k in range(20) : print(fibonacci(k), end=', ')

On peut maintenant afficher fibonacci(500) de façon quasi instantanée.

Notons \( a_n \) le nombre d'additions nécessaires au calcul de fibonacci(n). \( a_0 = a_1 = 0 \) et \( a_n = a_{n-1}+1 \).

On a donc \( a_n = n-1 \).

Pour calculer fibonacci(500), nous n'avons donc besoin que de 499 additions ! A comparer au nombre d'additions avec le premier script...

Une autre technique consiste à utiliser le premier script mais en mémorisant les calculs déjà effectués afin de ne pas les refaire.

La complexité en temps devient linéaire.

def fibonacci(n) :
	memoire = {0 : 1, 1 : 1 }

	def fibo(n) :
		if n in memoire : return memoire[n]
		else :
			f = fibo(n-1) + fibo(n-2)
			memoire[n] = f
			return f
	
	return fibo(n)
	
for k in range(20) :
	print( "F({}) = {}.".format(k, fibonacci(k) ) )

On peut maintenant afficher fibonacci(500) de façon quasi instantanée.

On peut également utiliser un décorateur :

def memorise(f):
    memoire = {}
    def seSouvenir(x):
        if x not in memoire : memoire[x] = f(x)
        return memoire[x]
    return seSouvenir
    
 
def fibonacci(n):
    if n <= 1 : return 1
    else : return fibonacci(n-1) + fibonacci(n-2)


fibonacci = memorise(fibonacci)
print(fibonacci(400))

De l'égalité \[ \left( \begin{matrix} F_{n+1} \\ F_n \end{matrix} \right) = \left( \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right) \times \left( \begin{matrix} F_{n } \\ F_{n -1}\end{matrix} \right) \] on déduit facilement : \[ \left( \begin{matrix} F_{n+1} \\ F_n \end{matrix} \right) = \left( \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right)^n \times \left( \begin{matrix} 1 \\ 1\end{matrix} \right) \]

def produit(A, B):
	"""
	A = [[a,b]
		 [c,d]]  matrice 2*2
	B est une autre matrice 2*2
	La fonction retourne le produit C des deux matrices
	"""
	C = [[0,0],[0,0]]
	for i in (0,1) :
		for j in (0,1) :
			C[i][j] = A[i][0]*B[0][j] + A[i][1]*B[1][j]
	return C


def puissance(A, n, p = [[1,0],[0,1]]) :
	"""
	A est une matrice 2*2.
	La fonction retourne A^n.
	"""
	if n == 0 : return p
	if (n%2 == 0) : return puissance(produit(A,A), n//2, p  )
	else : return puissance(produit(A,A), n//2, produit(p,A) )
        


def fibonacci(n) :
	A = [[1,1],[1,0]]
	F = puissance(A, n)
	return F[1][0] + F[1][1]
	
	
for k in range(20) :
	print(fibonacci(k))

Il ne reste plus quà constater que, dans la fonction puissance, le nombre d'appels à la fonction produit est en log(n) (voir cette fiche d'exercices). Comme chaque appel de produit fait intervenir un nombre constant d'opérations, on a bien au final une complexité en log(n).

• Avec \( p = n\) : \( F_{2n} = F_n^2 + F_{n-1}^2 \)
• Avec \( p = n-1\) : \( F_{2n-1} = F_{n-1} F_n + F_{n-1} F_{n-2} \). Avec \( F_{n-2} = F_n - F_{n-1} \), on obtient \( F_{2n-1} = F_{n-1} \times \left( 2F_n - F_{n-1} \right) \)
• De même, avec \( p = n+1\) : \( F_{2n+1} = F_n \left(F_n + 2F_{n-1} \right) \)

Posons \( U_n = \left( F_{n-1}, F_{n} \right) \). On voit que \( U_{2n} \), \( U_{2n+1} \) se calcule à partir de \( U_n \) :

• \( U_{2n} = \left( F_{n-1} \times \left( 2F_n - F_{n-1} \right) , F_n^2 + F_{n-1}^2 \right) \)
• \( U_{2n+1 } = \left( F_n^2 + F_{n-1}^2 , F_n \left(F_n + 2F_{n-1} \right) \right) \)

def fibonacci(n) :
	
	def f(n) :
		if n == 0 : return (0,1)
		elif n == 1 : return (1,1)
		else : 
			(u,v) = f(n//2)
			if n%2 == 0 :
				return ( u * (2*v - u), u*u + v*v)
			else :
				return ( u*u + v*v, v * (v + 2*u) )
			
	return f(n)[1]
 		
 		
for i in range(20) :
	print("F({}) = {}.".format(i, fibonacci(i)) )