Prérequis : fonctions en Python
, boucles for et while
À l’issue de ce chapitre, vous saurez :
Soient les deux affirmations suivantes :
Dans de nombreuses situations en programmation, il est pratique, voire essentiel, de diviser un problème en plusieurs parties. Dans certains cas, l’utilisation de boucles peut être non-intuitif et fastidieux, notamment dans les cas où il suffit de réutiliser des résultats antérieurs. C’est alors qu’intervient la récursivité.
Une fonction est récursive si, lors de son exécution, elle s’appelle elle-même et a une condition de terminaison (pour empêcher la fonction de s’appeler à l’infini).
def somme(liste):
total = 0
for i in range(len(liste)):
total = total + liste[i]
return total
print(somme([5, 7, 3, 8, 10]))
def somme(liste):
if len(liste) == 1:
return liste[0]
else:
return liste[0] + somme(liste[1:])
print(somme([5, 7, 3, 8, 10]))
Si la longueur de la liste est de 1, la fonction renvoie l’unique nombre qu’elle contient : c’est la condition de terminaison. Sinon, elle renvoie le premier élément auquel on ajoute les autres nombres de la liste. Quand tous les appels récursifs sont exécutés, la fonction atteint sa condition de terminaison et retourne le résultat.
En mathématiques, la factorielle d’un entier naturel \(n\), notée \(n!\), ce qui se lit soit « factorielle de \(n\) » soit « factorielle \(n\) », est le produit des nombres entiers strictement positifs inférieurs ou égaux à \(n\).
def factorielle(n):
k = 1
f = 1
while k <= n:
f = f * k
k = k + 1
return f
print(factorielle(3))
def factorielle(n):
if n == 0:
return 1
else:
return n * factorielle(n-1)
print(factorielle(3))
L’exécution de factorielle(3) fait appel à factorielle(2), qui fait appel à factorielle(1), qui fait appel à factorielle(0) : on atteint alors la condition de terminaison. Le calcul de factorielle(n) demande donc n + 1 appels : leur nombre augmente proportionnellement à n.
Dans une suite de Fibonacci, chaque nombre est la somme des deux nombres précédents, tels que : \(1 + 1 = 2 ; 1 + 2 = 3 ; 2 + 3 = 5 ; 3 + 5 = 8\). La suite de Fibonacci apparaît dans de nombreux domaines, de la botanique à l’algorithmique.
La suite de Fibonacci commence par \(0\) et \(1\). Le premier nombre dans une suite de Fibonacci est \(0\), le deuxième nombre est \(1\), et le troisième terme de la séquence est \(0 + 1 = 1\). Le quatrième est \(1 + 1 = 2\) et ainsi de suite.
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
prepre = 0
pre = 1
resultat = 0
for i in range(2, n + 1):
resultat = pre + prepre
prepre = pre
pre = resultat
return resultat
print(fibonacci(7))
Les deux cas de base qui correspondent à la condition de terminaison sont les valeurs \(0\) et \(1\). On a ainsi :
def fibonacci(n):
if n == 0 or n == 1:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(7))
Quand une fonction récursive s’appelle elle-même, Python empile un nouveau contexte d’exécution dans la pile d’appels. Chaque contexte contient les paramètres et variables locales de l’appel en cours.
Déroulons l’exécution de factorielle(4) :
À chaque appel, un nouveau cadre est empilé. Quand le cas de base est atteint, les cadres sont dépilés un par un, et chaque résultat est transmis à l’appelant. C’est pour cela que la récursivité consomme de la mémoire proportionnellement au nombre d’appels imbriqués.
Pour Fibonacci, la pile est plus complexe car chaque appel en génère deux :
Cette figure s’appelle l’arbre des appels : chaque case est un appel, reliée aux appels qu’il déclenche. On y lit que fibonacci(2) est calculé deux fois et fibonacci(1) trois fois. Plus n grandit, plus ces calculs répétés se multiplient : le nombre d’appels croît de façon exponentielle, et fibonacci(35) en demande près de trente millions.
La mémoïsation évite ces calculs répétés. On range chaque résultat dans un dictionnaire la première fois qu’on le calcule, puis on le relit au lieu de le recalculer :
memo = {}
def fibonacci_memo(n):
if n in memo: # déjà calculé : on relit le résultat
return memo[n]
if n == 0 or n == 1:
resultat = n
else:
resultat = fibonacci_memo(n - 1) + fibonacci_memo(n - 2)
memo[n] = resultat # on range le résultat avant de le renvoyer
return resultat
print(fibonacci_memo(35)) # 9227465, obtenu immédiatement
Chaque valeur n’est alors calculée qu’une seule fois : le nombre d’appels passe d’une croissance exponentielle à une croissance linéaire en n. Le chapitre sur la programmation dynamique généralise cette idée.
On voit que fibonacci(2) est calculé deux fois, ce qui explique la complexité exponentielle de cette version naïve.
def reverse(s):
if len(s) == 0:
return s
else:
return reverse(s[1:]) + s[0]
print(reverse("Python est un langage facile à apprendre"))
Chaque fois qu’une fonction s’appelle, elle stocke de la mémoire. Ainsi, une fonction récursive occupe souvent beaucoup plus de mémoire qu’une fonction traditionnelle. Python arrête les appels de fonction après une profondeur de 1000 appels. Si vous exécutez cet exemple :
def factorielle(n):
if n == 0:
return 1
else:
return n * factorielle(n-1)
print(factorielle(1500))
vous obtenez le message d’erreur suivant :
RecursionError: maximum recursion depth exceeded
Pour lever cette limite, on peut procéder de la manière suivante :
import sys
sys.setrecursionlimit(5000)
def factorielle(n):
if n == 0:
return 1
else:
return n * factorielle(n - 1)
print(factorielle(1500))
Ce qui n’est pas nécessairement la meilleure chose à faire pour des raisons de performance…
Dans le cas de la suite de Fibonacci, on préférera notamment la programmation dynamique :
def fibonacci(n):
fib = {0: 0, 1: 1}
for k in range(2, n + 1):
fib[k] = fib[k - 1] + fib[k - 2]
return fib[n]
print(fibonacci(7))
La récursivité n’est donc pas la meilleure solution à tous les problèmes mais elle s’avère très utile dans certains cas. Il suffit de l’utiliser à bon escient.
factorielle(n), quel est le cas de base ? Que se passe-t-il si on l’oublie ?
n == 0, pour que factorielle(0) renvoie 1. Sans lui, la fonction s'appelle indéfiniment et provoque un RecursionError.fibonacci(5) appelle-t-il fibonacci(2) ? Pourquoi est-ce un problème ?
RecursionError.fibonacci(k) a déjà été calculé, on renvoie directement le résultat. La complexité passe à $O(n)$.