Aller au contenu principal

La récursivité

Le principe​

Définition

Une fonction est dite récursive lorsqu'elle s'appelle elle-même au cours de son exécution.

L'idée peut sembler étrange : comment une fonction peut-elle s'utiliser elle-même alors qu'elle n'a pas encore terminé ?

Prenons un exemple simple : afficher les nombres de 3 à 0.

def compte_a_rebours(n):
    print(n)
    if n > 0:
        compte_a_rebours(n - 1)

Lorsqu'on appelle :

compte_a_rebours(3)

la fonction travaille successivement avec plusieurs valeurs de n :

compte_a_rebours(3)
    appelle compte_a_rebours(2)
        appelle compte_a_rebours(1)
            appelle compte_a_rebours(0)

Chaque appel exécute la même fonction, mais avec une valeur différente de n.

La récursivité consiste donc à ramener un problème à une version plus petite du même problème.

Cas d'arrêt et cas général​

Les deux questions essentielles

Une fonction récursive doit permettre de répondre à deux questions.

  • Quand doit-on s'arrêter ? C'est le cas d'arrêt.
  • Comment continuer sur un problème plus petit ? C'est le cas général.

Reprenons le compte à rebours :

def compte_a_rebours(n):
    if n == 0:                       # cas d'arrêt
        print(0)
    else:                            # cas général
        print(n)
        compte_a_rebours(n - 1)      # appel récursif

Dans cet exemple :

  • le cas d'arrêt correspond à n == 0 ;
  • le cas général correspond à n > 0 ;
  • l'appel compte_a_rebours(n - 1) rapproche progressivement du cas d'arrêt.
Point essentiel

Avoir un cas d'arrêt ne suffit pas. Chaque appel récursif doit se rapprocher de ce cas d'arrêt.

Par exemple, remplacer n - 1 par n + 1 empêcherait la fonction d'atteindre 0 si elle démarre avec un entier positif.

Sans arrêt correct, Python finit par interrompre le programme avec une erreur RecursionError.

Comprendre les appels successifs​

Lorsqu'une fonction appelle une autre fonction, Python doit mémoriser l'endroit où reprendre l'exécution lorsque l'appel sera terminé.

Pour cela, les appels en cours sont conservés dans une pile d'exécution.

Considérons :

def fonction_a():
    print("A")


def fonction_b():
    print("Début B")
    fonction_a()
    print("Fin B")


fonction_b()

Lorsque fonction_b() appelle fonction_a(), l'exécution de fonction_b() est temporairement mise en attente. Une fois fonction_a() terminée, Python reprend fonction_b() juste après l'appel.

Avec une fonction récursive, le principe est identique, sauf que plusieurs appels de la même fonction sont présents en même temps dans la pile.

Pour :

compte_a_rebours(3)

on peut représenter la pile ainsi :

compte_a_rebours(3)
└── compte_a_rebours(2)
    └── compte_a_rebours(1)
        └── compte_a_rebours(0)

Lorsque le cas d'arrêt est atteint, les appels se terminent ensuite dans l'ordre inverse.

Une fonction récursive qui renvoie une valeur​

La récursivité devient particulièrement intéressante lorsqu'un appel utilise le résultat de l'appel suivant.

On souhaite par exemple calculer la somme des entiers de 1 à n.

Pour n = 4 :

4 + 3 + 2 + 1

Mais on peut aussi voir ce calcul ainsi :

somme(4) = 4 + somme(3)
somme(3) = 3 + somme(2)
somme(2) = 2 + somme(1)
somme(1) = 1

On obtient alors :

def somme(n):
    if n == 1:
        return 1
    else:
        return n + somme(n - 1)

Pour comprendre somme(4), il faut distinguer deux phases.

Descente vers le cas d'arrêt :

somme(4)
= 4 + somme(3)
= 4 + 3 + somme(2)
= 4 + 3 + 2 + somme(1)

On atteint alors le cas d'arrêt :

somme(1) = 1

Remontée des résultats :

somme(1) = 1
somme(2) = 2 + 1 = 3
somme(3) = 3 + 3 = 6
somme(4) = 4 + 6 = 10
À comprendre

Dans l'instruction :

return n + somme(n - 1)

Python ne peut pas terminer le calcul tant qu'il ne connaît pas le résultat de somme(n - 1).

L'appel courant reste donc en attente pendant que l'appel suivant est exécuté.

Construire une fonction récursive​

Pour écrire une fonction récursive, on peut suivre toujours la même démarche.

Méthode
  1. Déterminer le cas d'arrêt.
  2. Déterminer la valeur ou l'action à effectuer dans ce cas.
  3. Déterminer le cas général.
  4. Écrire l'appel récursif sur un problème plus petit.
  5. Vérifier que cet appel se rapproche réellement du cas d'arrêt.

Par exemple, pour calculer 2n2^n :

2⁰ = 1
2ⁿ = 2 × 2ⁿ⁻¹

On en déduit directement :

def puissance2(n):
    if n == 0:
        return 1
    else:
        return 2 * puissance2(n - 1)

Le problème puissance2(n) est ainsi ramené au même problème avec une valeur plus petite : puissance2(n - 1).

Pourquoi utiliser la récursivité ?​

La récursivité n'est pas nécessaire pour tous les problèmes. Beaucoup de traitements peuvent aussi être réalisés avec une boucle.

Elle devient particulièrement naturelle lorsqu'un problème peut être décrit comme une combinaison de problèmes plus petits de même nature.

C'est notamment le cas pour :

  • parcourir des dossiers contenant eux-mêmes des sous-dossiers ;
  • parcourir certaines structures de données comme les arbres ;
  • effectuer certains calculs définis à partir de valeurs précédentes ;
  • construire des figures récursives comme des fractales.

L'objectif n'est donc pas de remplacer les boucles, mais d'apprendre une nouvelle manière de décomposer un problème.

À tester

Dérouler un programme dessinant un arbre en fractale étape par étape : Fichier exécutable