Récursivité

Introduction

Soient les deux affirmations suivantes :

• « Pour comprendre la récursivité, vous devez d’abord comprendre la récursivité »,
• « Un humain est quelqu’un dont la mère est humaine ».

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).

Un premier exemple : additionner tous les nombres d’une liste

Sans récursivité

def somme(liste):
    total = 0
    for i in range(len(liste)):
        total = total + liste[i]
    return total

print(somme([5, 7, 3, 8, 10]))

Avec récursivité

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.

Des exemples classiques

La factorielle

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\).

Sans récursivité

def factorielle(n):
    k = 1
    f = 1
    while k <= n:
        f = f * k
        k = k + 1
    return f

print(factorielle(3))

Avec récursivité

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.

La suite de Fibonacci

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.

Sans récursivité

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))

Avec récursivité

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))

La pile d’appels

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.

Inversion d’une chaîne de caractères

def reverse(s):
    if len(s) == 0:
        return s
    else:
        return reverse(s[1:]) + s[0]

print(reverse("Python est un langage facile à apprendre"))

Limites de la récursivité

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.