Récursivité : une fonction qui s'appelle elle-même

Une fonction est récursive lorsqu’elle s’appelle directement ou indirectement. Dans les exemples de cette leçon, les appels portent sur une donnée naturelle plus petite ; c’est ce qui permettra de justifier l’arrêt. Elle repose sur deux éléments :

1. un cas de base, traité directement, sans appel récursif ;
2. un cas récursif, qui ramène le problème à un problème plus petit du même type.

Dans les fonctions numériques de cette leçon, n est un entier naturel. La factorielle de n, notée n !, est le produit 1 × 2 × … × n, avec 0! = 1. Elle vérifie n ! = n × (n − 1)! : c'est un cas récursif tout trouvé.

def factorielle(n):
    if n == 0:
        return 1
    return n * factorielle(n - 1)

print(factorielle(5))

120

L'appel factorielle(5) déclenche factorielle(4), qui déclenche factorielle(3)… jusqu'au cas de base factorielle(0), qui renvoie 1 sans rien rappeler. Les résultats remontent ensuite : 1, puis 1 × 1, 2 × 1, 3 × 2, 4 × 6, 5 × 24 = 120.

Chaque appel en attente garde ses propres variables : le système les empile dans la pile des appels. Le dernier appel lancé est le premier terminé. Ce programme le rend visible :

def compte(n):
    if n == 0:
        print("décollage")
    else:
        print(n)
        compte(n - 1)
        print("retour de", n)

compte(3)

3
2
1
décollage
retour de 1
retour de 2
retour de 3

Les messages « retour de » s'affichent dans l'ordre inverse des appels : compte(1) termine en premier, compte(3) en dernier.

Terminaison. La terminaison mathématique des exemples se justifie par une donnée entière naturelle qui diminue strictement jusqu’au cas de base. En pratique, une récursion même terminante peut dépasser la limite de profondeur de Python avant de l’atteindre. Sans cas de base, ou avec une donnée qui ne diminue pas, les appels s'empilent sans fin et Python interrompt le programme avec une erreur RecursionError.

Un coût parfois caché. Une fonction qui s'appelle DEUX fois peut recalculer très souvent les mêmes valeurs :

appels = []

def fibo(n):
    appels.append(n)
    if n < 2:
        return n
    return fibo(n - 1) + fibo(n - 2)

print(fibo(10), len(appels))

55 177

Pour obtenir fibo(10) = 55, la fonction est appelée 177 fois : fibo(2), par exemple, est recalculé de nombreuses fois. La programmation dynamique, au programme de terminale, évite ces recalculs en mémorisant les résultats.

Énoncé. Que renvoie somme_chiffres(4705) ?

def somme_chiffres(n):
    if n < 10:
        return n
    return n % 10 + somme_chiffres(n // 10)

print(somme_chiffres(4705))

Déroulé. n % 10 est le chiffre des unités, n // 10 le nombre privé de ce chiffre.

En remontant : 4, puis 7 + 4 = 11, puis 0 + 11 = 11, puis 5 + 11 = 16.

16