5.5. La récursivité¶

Il est possible qu’une fonction fasse appelle à elle-même dans son corps d’instructions, créant ainsi une forme de boucle. On la qualifie alors de fonction récursive. Il faudra bien entendu veiller à ne pas créer de boucles d’appels récursifs infinies et donc s’assurer que la fonction comprend une condition d’arrêt.

Écrivons une fonction qui a pour but d’afficher une chaîne de caractères n fois dans la console, en utilisant la récursivité plutôt qu’une boucle. La fonction prendra en paramètres la chaîne à afficher ainsi que le nombre d’affichages désirés.

def print_n(s, n):         # affiche `s` dans la console `n` fois
    print(s)               # on affiche la chaîne
    if n > 0:              # condition d'arrêt : tant qu'il reste des lignes à afficher...
        print_n(s, n - 1)  # on recommence avec la même chaîne mais un affichage de moins


print_n("Je suis affiché... tant de fois !", 5)

Je suis affiché... tant de fois !
Je suis affiché... tant de fois !
Je suis affiché... tant de fois !
Je suis affiché... tant de fois !
Je suis affiché... tant de fois !

Cet exemple n’est bien entendu qu’une démonstration élémentaire de la récursivité : il serait à la fois plus simple et plus lisible d’utiliser une boucle for ou while. Pour mieux comprendre l’avantage de la récursivité, voyons à présent quelques problèmes concrets qui peuvent se résoudre naturellement de manière récursive.

5.5.1. Récursivité avec valeurs de retour¶

Considérons le problème du calcul du produit de deux nombres en utilisant uniquement des additions. On peut aisément le résoudre à l’aide d’une fonction récursive avec valeur de retour.

def multiply(a, b):                # calcule le produit de `a` et `b`
    if b == 0:                     # si `b` est égal à 0...
        return 0                   # on revoie 0
    return a + multiply(a, b - 1)  # sinon, on renvoie `a` + le produit de `a` et (`b` - 1)


print(multiply(6, 9))
print(multiply(0, 98))
print(multiply(multiply(13, 7), 234))

54
0
21294

5.5.2. La fonction factorielle¶

Une fois la difficulté de leur lecture surmontée, les fonctions récursives peuvent sembler plus intuitives que leur pendant itératif. Un exemple concret est la fonction factorielle, que l’on définit souvent en mathématiques sous la forme suivante :

\[\begin{split}n! = \begin{cases} n \cdot (n-1)! & n > 1\\ 1 & n = 1\\ \end{cases}\end{split}\]

Dans cette définition, la forme récursive apparaît clairement et devient simple à convertir en code Python. Essayons donc d’écrire notre fonction de deux manières, en utilisant tout d’abord une boucle.

def factorial(n):
    product = 1              # le produit total est initialisé à 1
    for x in range(1, n+1):  # pour chaque entier `x` entre 1 et `n`...
        product *= x         # on multiplie le produit total par `x`
    return product           # on renvoie le produit


print(factorial(3))
print(factorial(5))
print(f"{factorial(22):,}")

6
120
1,124,000,727,777,607,680,000

Écrivons à présent la même fonction de manière récursive.

def factorial(n):
    if n == 1:                 # si `n` vaut 1...
        return 1               # on renvoie 1 (condition d'arrêt)
    return n * factorial(n-1)  # sinon, on renvoie `n` * la factorielle de `n` - 1

La version récursive produit le même résultat. Elle a l’avantage d’être compacte et élégante, avec une structure très proche de la formulation mathématique de la fonction factorielle.

5.5.3. La suite de Fibonacci¶

La suite de Fibonacci est une suite de nombres débutant par [0, 1] et dont chaque terme vaut la somme des deux précédents. Plus formellement :

\[\begin{split}f(n) = \begin{cases} 0 & n = 0\\ 1 & n = 1\\ f(n-1) + f(n-2) & \text{sinon} \end{cases}\end{split}\]

Voici comment on peut trouver le n-ième (en comptant à partir de zéro) terme de la suite grâce à une fonction récursive.

def fib(n):
    if n <= 1:                      # si n est plus petit ou égal à 1 (ici, 0 ou 1)...
        return n                    # on renvoie `n` (donc 0 ou 1)
    return fib(n - 1) + fib(n - 2)  # sinon, on renvoie la somme des deux termes précédents


for n in range(10):
    print(fib(n))

À titre de comparaison, voyons à quoi pourrait ressembler une version non récursive de cette fonction. On pourra observer que la version récursive est plus lisible et intuitive, tout en étant plus succincte.

def fib(n):
    if n == 0:                    # le premier terme est 0
        return 0
    prev = [0, 1]                 # on mémorise les deux termes précédents
    for _ in range(n - 1):        # on calcule tous les termes jusqu'au `n`-ième
        next = prev[0] + prev[1]  # le terme suivant est la somme des deux précédents
        prev[0] = prev[1]         # on décale les anciens termes
        prev[1] = next            # on se souvient du nouveau terme
    return prev[1]                # à la fin de la boucle, on a le résultat

Introduction à la programmation avec Python (I)

5.5. La récursivité¶

5.5.1. Récursivité avec valeurs de retour¶

5.5.2. La fonction factorielle¶

5.5.3. La suite de Fibonacci¶