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):
    somme = 0
    for i in range(len(liste)):
        somme = somme + liste[i]
    return somme

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 elle-même fait appel à factorielle(1): on atteint alors la condition de terminaison. On remarque que le nombre d’appels récursifs peut croître très rapidement.

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

factorielle(4)
│ return 4 * factorielle(3)
│   │ return 3 * factorielle(2)
│   │   │ return 2 * factorielle(1)
│   │   │   │ return 1          ← cas de base
│   │   │ return 2 * 1 = 2
│   │ return 3 * 2 = 6
│ return 4 * 6 = 24

À 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 :

fibonacci(4)
├── fibonacci(3)
│   ├── fibonacci(2)
│   │   ├── fibonacci(1) → 1
│   │   └── fibonacci(0) → 0
│   │   → 1
│   └── fibonacci(1) → 1
│   → 2
└── fibonacci(2)
    ├── fibonacci(1) → 1
    └── fibonacci(0) → 0
    → 1
→ 3

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

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

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 = {}
    for k in range(1, n + 1):
        if k <= 2:
            f = 1
        else:
            f = fib[k - 1] + fib[k - 2]
        fib[k] = f
    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.