Utiliser la récursivité permet d’écrire des programmes très élégants et faciles à vérifier (c’est à dire qu’on se convainc (voire on prouve) aisément qu’ils sont justes). Mais les solutions récursives sont parfois très peu efficaces (temps de calcul prohibitifs). Dans ces cas de figure, il existe parfois des solutions pour régler le problème de l’efficacité comme la programmation dynamique ou le principe de memoïsation.
C’est au second que nous allons nous intéresser, et nous l’illustrerons en Python.
Quelques fonctions récursives
Factorielle récursive : pas de problème
Voici un premier exemple de fonction qui calcule la factorielle d’un nombre positif.
def factorielle(n):
if n < 2:
return 1
return factorielle(n - 1) * n
Pour compter, de manière expérimentale, combien d’appels à la fonction sont exécutés pour calculer la factorielle d’un nombre, nous allons utiliser une variable globale (c’est mal…) :
def factorielle(n):
global count_exe
count_exe = count_exe + 1
if n < 2:
return 1
return factorielle(n - 1) * n
Voyons ce que cela donne :
>>> count_exe = 0
>>> factorielle(10)
3628800
>>> count_exe
10
>>> count_exe = 0; factorielle(15)
1307674368000
>>> count_exe
15
Rien de bien surprenant. Pour calculer factorielle(n), on exécute n appels.
Passons à autre chose…
Suite de fibonacci récursive : ça se corse un peu
La suite de Fibonacci est définie ainsi:
$F_{n+2} = F_{n+1} + F_{n}$ et $F_0 = 0, F_1 = 1$
La fonction récursive (avec le compteur d’appels) est très simple :
def fibonacci(n):
global count_exe
count_exe = count_exe + 1
if n < 2:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
Testons notre fonction:
>>> count_exe = 0; fibonacci(6)
8
>>> count_exe
25
>>> count_exe = 0; fibonacci(15)
610
>>> count_exe
1973
Cette fois-ci, le nombre d’appels de la fonction semble grandir bien plus
vite que le paramètre n de la fonction. En fait, le nombre d’appel se comporte
ici à peu près comme les termes de la suite… et il grandit donc très vite.
Par exemple, pour calculer un
nombre comme fibonacci(30), qui ne vaut que 832040, la machine exécutera
2692537 appels à la fonction fibonacci.
Le nombre fibonacci(50) reste hors de portée de notre implémentation…
Il ne vaut pourtant que 12586269025.
Le problème est ici que notre fonction recalcule de très nombreuses fois la même chose.
En effet, le calcul de fibonacci(3) implique le calcul de fibonacci(2) et de
fibonacci(1). Mais le calcul de fibonacci(2) implique lui aussi le calcul de
fibonacci(1). Pour obtenir la valeur de fibonacci(30),
notre fonction récursive exécutera par exemple 121393 fois le calcul de fibonacci(5).
Voici un arbre des appels obtenu avec le module rcviz
qui détaille le calcul de fibonacci(6) (noté F(6) pour
aérer un peu le graphe). On y retrouve les 25 appels de fonction et on constate surtout que
certains sont réalisés plusieurs fois (le calcul de F(4), par exemple,
est nécessaire au calcul de F(6) ainsi qu’au calcul de F(5)):
Évidemment, rien ne nous oblige à calculer les termes de la suite de Fibonacci de manière récursive. La version itérative serait ici très simple.
Il est en effet immédiat de constater que pour calculer fibonacci(10), il faut avoir calculé
très exactement toutes les valeurs de fibonacci(n) pour n allant de 0 à 9, sans exception.
On pourrait même remarquer que seules les deux dernières valeurs (n-1 et n-2) sont nécessaires au calcul
de la valeur suivante (n). On n’a donc besoin de stocker que les deux dernières valeurs calculées :
def fibo_iter(n):
if n < 2: return n
a, b = 0, 1
for k in range(2,n+1):
a, b = b, a + b
return b
C’est un peu moins lisible que la version récursive, mais ça reste assez simple.
Ça se complique…
Il y a des cas où, contrairement à ce que nous pouvons faire sur la suite de Fibonacci, il est difficile de déterminer à l’avance quelles seront les valeurs nécessaires au calcul de la fonction pour des arguments donnés.
La fonction d’Ackermann est définie ainsi :
- $A(0,n) = n+1$
- si $m > 0$, $A(m,0) = A(m-1,1)$
- si $m > 0$ et $n > 0$, $A(m,n) = A(m-1, A(m, n-1))$
Le code est immédiat et très simple à trouver, car complétement calqué sur la définition.
def A(m,n):
if m == 0:
return n + 1
if n == 0:
return A(m - 1, 1)
return A(m - 1, A(m, n - 1))
Voyons ce que ça donne :
>>> A(3,2)
29
Voici l’arbre des appels de A(3,2), réalisé ici aussi avec rcviz:
Le calcul de A(3,2) (qui vaut 29) a nécessité 541 appels (c’est le nombre de nœuds
du graphe précédent).
Si nous voulons faire comme pour la suite de Fibonacci, il faut savoir quels sont les $A(i,k)$ nécessaires au calcul d’un $A(m,n)$ particulier. Pas évident…
Vers une solution
Nous cherchons donc un moyen :
- de conserver l’écriture récursive, car elle est simple et élégante, et il est parfois difficile d’en trouver une autre ;
- de ne pas refaire plusieurs fois le même calcul ;
- de ne pas non plus faire (même une seule fois) des calculs qui ne sont pas nécessaires.
Memoïsation en Python : fastoche
La memoïsation est une manière d’éviter de recalculer plusieurs fois les mêms résultats, en les stockant tout simplement au fur et à mesure qu’ils sont calculés.
Sans décorateur
Il y a plusieurs manières de procéder. Certaines nécessitent que l’on modifie la fonction d’origine. D’autres utilisent les décorateurs Python. Mais le principe reste le même : stocker les résultats des calculs dans une structure de données appropriée. Avec Python, cette structure est toute trouvée : un dictionnaire. La clé du dictionnaire sera le n-uplet (tuple) formé par les arguments utilisés lors de l’appel de la fonction et la valeur associée à cette clé sera le résultat renvoyé lors de cet appel. Pour que ça fonctionne, il faut que la clé du dictionnaire, et donc les paramètres de la fonction soient de type hachable. Tous les types non-mutables, comme les scalaires numériques, les chaînes de caractères, les tuples etc… sont hachables : ils peuvent être utilisés comme clé d’un dictionnaire.
Ici, nous allons nous contenter de fonctions dont les paramètres sont des nombres. Il n’y a donc aucune difficulté : nous utiliserons comme clé le tuple formé par les arguments de la fonction.
Voici la fonction fibonacci modifiée de manière à stocker ses résultats
dans un dictionnaire (memo_fibo) :
memo_fibo = dict()
def fibonacci(n):
global count_exe
count_exe = count_exe + 1
if n in memo_fibo:
return memo_fibo[n]
if n < 2:
memo_fibo[n] = n
else:
memo_fibo[n] = fibonacci(n - 1) + fibonacci(n - 2)
return memo_fibo[n]
Bon… c’est pas très joli, mais ça fonctionne. Le dictionnaire
memo_fibo est initialement vide. Lorsqu’on entre dans la fonction
avec le paramètre $n$, s’il y a déjà un résultat dans le
dictionnaire (à la clé $n$) ce résultat est renvoyé. Sinon, on
calcule le résultat, on le stocke dans le dictionnaire, et on le renvoie.
Voyons ce qui se produit à présent pour le calcul de fibonacci(15),
sachant qu’avec la version précédente, nous générions 1973 appels :
>>> count_exe = 0; fibonacci(15)
610
>>> count_exe
29
Et voilà ! Maintenant, fibonacci(50) est à notre portée :
>>> count_exe = 0; fibonacci(50)
12586269025
>>> count_exe
71
On a besoin de 71 appels seulement, alors qu’il en aurait fallu 40730022147 dans la version sans memoïsation.
Avec décorateur : améliorons un peu l’écriture
Pour rendre notre version si efficace un peu moins moche, on peut attacher le dictionnaire à la fonction (une fonction est un objet, on peut donc lui ajouter des attributs (nous avions vu ça dans le billet Variables statiques en Python).
En plus de ça, nous allons utiliser un décorateur. N’importe quelle fonction pourra donc être transformée en fonction utilisant la memoïsation sans qu’on ait besoin de lui apporter la moindre modification interne. Voici le code de notre décorateur :
def memoize(f):
def decorated(*args):
if args not in decorated.memo:
decorated.memo[args] = f(*args)
return decorated.memo[args]
decorated.memo = dict()
return decorated
Il pourra fonctionner avec n’importe quelle fonction
ne comportant aucun paramètre nommé (nous n’avons utilisé que *args
dans le décorateur), et dont tous les paramètres sont hachables, car
ils seront utilisés comme clé du dictionnaire.
C’est le cas pour les fonctions ayant des nombres pour paramètres.
La fonction ne doit pas avoir d’effet de bord non plus (modification d’une variable globale par exemple…), ou alors il faut le maîtriser.
Nous pouvons maintenant simplement écrire :
@memoize
def factorielle(n):
if n < 2:
return 1
return factorielle(n - 1) * n
@memoize
def fibonacci(n):
if n < 2:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
@memoize
def A(m,n):
if m == 0:
return n + 1
if n == 0:
return A(m - 1, 1)
return A(m - 1, A(m, n - 1))
Nos trois fonctions s’utilisent tout à fait normalement, et on peut même consulter le dictionnaire qui stocke les résultats et ainsi savoir quelles évaluations ont été nécessaires :
>>> factorielle(10)
3628800
>>> factorielle.memo
{(10,): 3628800,
(5,): 120,
(6,): 720,
(1,): 1,
(7,): 5040,
(2,): 2,
(8,): 40320,
(3,): 6,
(9,): 362880,
(4,): 24}
>>> fibonacci(6)
8
>>> fibonacci.memo
{(5,): 5, (0,): 0, (6,): 8,
(1,): 1, (2,): 1, (3,): 2, (4,): 3}
>>> A(2,2)
7
>>> A.memo
{(0, 1): 2, (1, 2): 4, (1, 3): 5, (0, 6): 7,
(2, 2): 7, (2, 1): 5, (1, 1): 3, (2, 0): 3,
(0, 5): 6, (1, 4): 6, (0, 4): 5, (1, 5): 7,
(1, 0): 2, (0, 3): 4, (0, 2): 3}
L’utilisation de la mémoïzation permet donc, dans certains cas, d’utiliser directement le code récursif naïf et de le rendre beaucoup plus efficace. Gardons à l’esprit qu’une solution itérative est toujours possible, même si elle est parfois difficile à trouver (on trouvera des informations complémentaires sur literateprograms, ici, et dans cet article).
Python contient déjà un décorateur pour faire de la mémoïsation dans le module functools.
Vous trouverez des informations dans Mémoïsation : le retour.
La memoïsation peut être utilisée dans les challenges Pydéfis suivants :
- Choix Cornéliens
- Suite Q(n)
- …