Fonction récursive :¶
Une fonction qui s'appelle elle-même ...
def ma_premiere_fonction_recursive(n):
...
ma_premiere_fonction_recursive(...)
....
NB : z = f(f(3)) n'est pas de la récursité. Il y a deux appels successifs à f¶
Exemple 1 : sommer les entiers de 0 à n¶
Version itérative¶
def sommeIt(n):
s = 0
for i in range(n+1):
s += i
return s
sommeIt(5)
15
Version optimisée "mathématiquement"¶
def sommeFormule(n):
return n*(n+1)//2
sommeFormule(5)
15
Version récursive¶
On pose $S_n = \sum_{i=0}^n i$
$S_0 = 0$, et pour $n>0$, $S_n = S_{n-1} + n$ ...
def sommeR(n):
if n==0:
return 0
else:
s = sommeR(n-1)
return s+n
sommeR(5)
15
magique ???
Avec Python Tutor
Appels imbriqués¶
Les appels imbriqués se font dans un ordre précis, celui dicté par le programme
Pour répondre au problème $n$, on s'aide de la réponse au problème $n-1$, qui s'aide de la réponse au problème $n-2$ ... ainsi de suite ...
et la réponse au problème 0 est triviale
Attention aux analogies mathématiques¶
On pose $S_n = \sum_{i=0}^n i$. Certes $S_n = n + S_{n-1}$ ...
Mais ce n'est pas ce genre d'égalité à elle seule qui justifie que tout se passe bien ...
def sommeR(n):
s = sommeR(n+1)
return s - (n+1)
Avec Pyton Tutor
un appel à cette fonction ne termine pas
Attention : limitation du nombre d'appels imbriqués¶
sommeR(3000)
--------------------------------------------------------------------------- RecursionError Traceback (most recent call last) <ipython-input-4-a1a601c64b2a> in <module> ----> 1 sommeR(3000) <ipython-input-2-f912480cd332> in sommeR(n) 3 return 0 4 else: ----> 5 s = sommeR(n-1) 6 return s+n 7 ... last 1 frames repeated, from the frame below ... <ipython-input-2-f912480cd332> in sommeR(n) 3 return 0 4 else: ----> 5 s = sommeR(n-1) 6 return s+n 7 RecursionError: maximum recursion depth exceeded in comparison
Exemple 2 : le nième terme de la suite de Fibonacci¶
Suite mathématique célèbre : 0 ; 1 ; 1 ; 2 ; 3 ; 5 ; 8 ; 13 ; 21 ; 34 ; 55 ... (une histoire de reproduction de lapins ...) définie par :
$u_0 = 0$, $u_1 = 1$ et $\forall n \in \mathbb{N}\setminus\{0;1\}$, $u_{n}=u_{n-1}+u_{n-2}$
Et comme par magie, on peut définir ...
def fibo(n):
if n==0:
return 0
elif n==1:
return 1
else:
a = fibo(n-2)
b = fibo(n-1)
return a+b
fibo(6)
8
avec Python Tutor
Il y a de trop nombreux appels, souvent identiques ... (c'est beaucoup moins magique ...)
Attention : appels répétés¶
import time
t1 = time.time()
z = fibo(33) # version récursive
t2 = time.time()
print(z)
print(t2-t1) # durée d'éxecution
3524578 2.993722677230835
NB : 3 secondes de calcul pour obtenir le 33ième terme de la suite (c'est beaucoup trop long !)
Mémoïsation¶
Principe : on conserve les résultats des appels déjà réalisés (cf TP Récursivité)
def fibo_memo(memo, n):
if memo[n] != -1:
return memo[n]
else :
v = fibo_memo(memo,n-2) + fibo_memo(memo,n-1)
memo[n] = v
return v
def fibo2(n):
memo = [-1]*(n+1)
memo[0] = 0
memo[1] = 1
return fibo_memo(memo,n)
import time
t1 = time.time()
z = fibo2(33) # version mémoïsée
t2 = time.time()
print(z)
print(t2-t1) # durée d'éxecution
3524578 0.00041675567626953125
NB : quelques micro-secondes de calcul pour obtenir le 33ième terme de la suite
