Qu'est-ce que la récursivité en Python ?

En récursivité, une fonction s'appelle elle-même pour résoudre un problème. Cependant, pour qu'une fonction récursive soit valide et ne tourne pas à l'infini, elle doit respecter deux règles :

La condition d'arrêt qui permet à la fonction de s'arrêter sans s'appeler de nouveau
L'appel récursif avec des données modifiées dans le but d'atteindre le cas de base

Rassurez-vous, vous ne vous retrouverez pas réellement dans une récursion infinie ; Python lèvera une RecursionError car la mémoire sera saturée.

Quelques exemples de récursivité

Le compte à rebours

def compte_a_rebours(n):
    # 1. Cas de base : on arrête quand n est 0 ou moins
    if n <= 0:
        print("Décollage !")
    else:
        # Action de la fonction
        print(n)

        # 2. Appel récursif : on rappelle la fonction avec n - 1
        compte_a_rebours(n - 1)

# Utilisation
compte_a_rebours(3)
# Affichera :
# 3
# 2
# 1
# Décollage !

PYTHON

Un instant

Créez un compte pour exécuter ce code

Inscrivez-vous gratuitement pour modifier et exécuter du code Python directement dans votre navigateur.

Se connecter Créer un compte

compte_a_rebours(3) affiche 3, puis appelle compte_a_rebours(2)
compte_a_rebours(2) affiche 2, puis appelle compte_a_rebours(1)
compte_a_rebours(1) affiche 1, puis appelle compte_a_rebours(0)
compte_a_rebours(0) atteint le cas de base, affiche "Décollage !" et la chaîne d'appels s'arrête

Cet exemple permet de visualiser la descente, c'est-à-dire les appels successifs de la fonction.

À noter

Il faut noter qu'avec cet exemple simple, on ne voit pas encore le principe de remontée. Mais en réalité, une fois à compte_a_rebours(0), on revient dans la fonction pour 1 qui se termine, puis pour 2 qui se termine, et enfin 3 qui se termine.

Mais comme il n'y a pas de code après l'appel récursif, rien ne s'exécute.

Comprendre la remontée

On a parlé de la descente, mais il faut aussi visualiser la remontée. Reprenons le code précédent en y ajoutant un message après l'appel récursif :

def compte_a_rebours(n):
    # 1. Cas de base : on arrête quand n est 0 ou moins
    if n <= 0:
        print("Décollage !")
    else:
        # Action de la fonction
        print(n)

        # 2. Appel récursif : on rappelle la fonction avec n - 1
        compte_a_rebours(n - 1)
        print("après l'appel récursif de", n)

# Utilisation
compte_a_rebours(3)
# Affichera :
# 3
# 2
# 1
# Décollage !
# après l'appel récursif de 1
# après l'appel récursif de 2
# après l'appel récursif de 3

PYTHON

Un instant

Créez un compte pour exécuter ce code

Inscrivez-vous gratuitement pour modifier et exécuter du code Python directement dans votre navigateur.

Se connecter Créer un compte

Le résultat est un peu déroutant ?

En fait, chaque appel de fonction attend que l'appel récursif se termine avant de continuer son propre code. Cette fois-ci, on remonte la pile !

Le grand classique : la factorielle

La factorielle est l'exemple le plus commun de récursivité. La factorielle de 5 est 1 × 2 × 3 × 4 × 5.

def factorielle(n):
    # Cas de base : la factorielle de 1 (ou 0) vaut 1
    if n <= 1:
        return 1

    # Appel récursif
    return n * factorielle(n - 1)

resultat = factorielle(5)
print(f"La factorielle de 5 est : {resultat}")  # Affiche 120

PYTHON

Un instant

Créez un compte pour exécuter ce code

Inscrivez-vous gratuitement pour modifier et exécuter du code Python directement dans votre navigateur.

Se connecter Créer un compte

À noter

Dans le compte à rebours, on attendait juste la fin de l'appel. Ici, on attend le résultat de l'appel pour l'utiliser. En fait, le mot-clé return attend le résultat de l'appel pour l'utiliser.

Bien qu'il n'y ait pas de ligne de code visible sous le return, l'opération n * ... est mise en attente. Pour calculer 5 * factorielle(4), Python doit d'abord connaître le résultat de factorielle(4), et ainsi de suite.

Première étape :

factorielle(5) veut faire 5 * factorielle(5 - 1), appelle donc factorielle(4)
factorielle(4) veut faire 4 * factorielle(4 - 1), appelle donc factorielle(3)
Ainsi de suite jusqu'à 1

Deuxième étape :

factorielle(2) récupère 1, calcule 2 * 1 et retourne 2
factorielle(3) récupère 2, calcule 3 * 2 et retourne 6
factorielle(4) récupère 6, calcule 4 * 6 et retourne 24
factorielle(5) récupère 24, calcule 5 * 24 et retourne 120

Pour conclure :

Le compte à rebours retourne implicitement None, l'appelant reçoit None, il l'ignore et continue de s'exécuter
La factorielle retourne le résultat de l'appel récursif pour construire sa réponse, le return crée une dépendance entre les appels, car il dépend de la valeur renvoyée par l'enfant

Qu'est-ce que la récursivité en Python ?