Récursivité

Le programme

La récursivité est un style de programmation permettant de simplifier l'écriture de nombreux problèmes.

Un peu de culture

La récursivité, en informatique, est une pratique qui permet à une fonction de s'appeler elle-même. On peut comparer cela à la mise en abyme, procédé littéraire qui décrit une œuvre incrustée dans elle-même.

La fonction récursive s'appelle elle-même dans sa définition.

---

Mauvais exemple

Rien de tel qu'un mauvais usage pour mieux comprendre un concept.

Voici une fonction récursive :

def fct_recursive() :
    print("Je fais un appel de la fonction")
    fct_recursive()

Cette fonction s'appelle elle-même, mais elle présente un problème.

Si nous l'appelons, le résultat sera celui-ci :

>>> fct_recursive()
"Je fais un appel de la fonction"
"Je fais un appel de la fonction"
"Je fais un appel de la fonction"
"Je fais un appel de la fonction"
"Je fais un appel de la fonction"
"Je fais un appel de la fonction"
"Je fais un appel de la fonction"
...

Tout comme les boucles, il faut créer une instruction permettant d'arrêter l'exécution du code, en récursif nous l'appelons le cas de base (ou cas d'arrêt). Il permettra d'éviter les appels infinis.

Le cas de base

Afin de stopper l'exécution du code il est donc essentiel de créer une instruction n'appelant pas notre fonction.

Par exemple :

Voici la fonction somme(n) se définissant comme :

\[ somme(n) = \begin{cases} 0 & \text{si } n = 0 \text{ (cas de base)}\\ n + somme(n-1) & \text{sinon (cas récursif)} \end{cases} \]

def somme(n) :
    if n == 0 :
        return 0        # Cas de base
    else :
        return n + somme(n-1)   # Cas récursif

Cette fonction s'appelle donc elle-même jusqu'à avoir n égal à 0.

Mais quel sera le résultat de somme(3) ?

Pour obtenir cette réponse nous allons dérouler à la main le code :

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

Voici les différents appels de fonctions pour somme(3). Mais là, le résultat n'est pas encore obtenu.

Pour cela il faut reprendre les appels de fonctions pour revenir jusqu'à somme(3) :

somme(0) = 0
somme(1) = 1 + 0 = 1
somme(2) = 2 + 1 = 3
somme(3) = 3 + 3 = 6

Ici nous observons donc 4 appels de fonctions pour résoudre somme(3).

---

La pile d'appels

Lorsqu'une fonction récursive s'exécute, Python utilise une structure de données appelée pile d'appels (ou call stack) pour gérer les différents appels.

Principe de fonctionnement

À chaque appel de fonction : 1. Python empile un nouveau contexte d'exécution contenant les paramètres et variables locales 2. Lorsque le cas de base est atteint, les appels sont dépilés un par un 3. Chaque résultat remonte vers l'appel précédent

Visualisation avec somme(3)

                    EMPILEMENT                          DÉPILEMENT
                    (descente)                          (remontée)

    ┌─────────────┐                         ┌─────────────┐
    │  somme(0)   │  ← cas de base          │  somme(0)   │ → retourne 0
    ├─────────────┤                         ├─────────────┤
    │  somme(1)   │  attend somme(0)        │  somme(1)   │ → retourne 1+0 = 1
    ├─────────────┤                         ├─────────────┤
    │  somme(2)   │  attend somme(1)        │  somme(2)   │ → retourne 2+1 = 3
    ├─────────────┤                         ├─────────────┤
    │  somme(3)   │  attend somme(2)        │  somme(3)   │ → retourne 3+3 = 6
    └─────────────┘                         └─────────────┘
         BASE                                    BASE

La pile fonctionne selon le principe LIFO (Last In, First Out) : le dernier appel empilé est le premier à être résolu.

---

Limite de récursion en Python

En Python il existe une limite au nombre d'appels de fonction que l'on peut faire pour une fonction récursive.

En effet, avec notre exemple nous voyons que pour obtenir somme(3) nous faisons 4 appels de fonction.

Ces appels de fonction s'empilent en espace mémoire. Python peut stocker environ 1000 appels par défaut.

Si cette limite est dépassée alors l'erreur RecursionError apparaîtra :

>>> somme(1001)
...
RecursionError: maximum recursion depth exceeded in comparison

Cette limite existe pour protéger la mémoire de l'ordinateur. On peut la modifier avec sys.setrecursionlimit(), mais ce n'est généralement pas recommandé.

---

Terminaison d'une fonction récursive

Une question essentielle se pose : comment être sûr qu'une fonction récursive s'arrête ?

Le variant de boucle

Pour prouver qu'une fonction récursive termine, on utilise un variant : une quantité entière qui : - est positive ou nulle à chaque appel - décroît strictement à chaque appel récursif

Quand le variant atteint 0 (ou une valeur minimale), on est dans le cas de base.

Exemple avec somme(n)

Pour la fonction somme(n) : - Variant : la valeur de n - À chaque appel récursif, on appelle somme(n-1), donc n décroît de 1 - Quand n = 0, on atteint le cas de base

Appel	Valeur du variant (n)
somme(3)	3
somme(2)	2
somme(1)	1
somme(0)	0 → cas de base

Le variant décroît strictement et atteint 0 : la fonction termine.

Attention aux erreurs

def mauvaise_somme(n):
    if n == 0:
        return 0
    else:
        return n + mauvaise_somme(n + 1)  # n augmente !

Ici, le paramètre augmente au lieu de diminuer : la fonction ne terminera jamais (jusqu'à la RecursionError).

---

Écrire une fonction récursive : méthodologie

Pour écrire correctement une fonction récursive, il faut identifier trois éléments :

Élément	Question à se poser	Exemple avec somme(n)
Cas de base	Quel est le cas le plus simple, qui ne nécessite pas d'appel récursif ?	n == 0 → retourne 0
Cas récursif	Comment décomposer le problème en un sous-problème plus petit ?	somme(n) = n + somme(n-1)
Variant	Quelle quantité décroît à chaque appel ?	La valeur de n

Exemple : la factorielle

On souhaite écrire factorielle(n) qui calcule n! = n × (n-1) × ... × 2 × 1.

1. Cas de base : factorielle(0) = 1 (par convention, 0! = 1)
2. Cas récursif : factorielle(n) = n × factorielle(n-1)
3. Variant : n décroît de 1 à chaque appel

def factorielle(n):
    if n == 0:
        return 1                        # Cas de base
    else:
        return n * factorielle(n - 1)   # Cas récursif

Vérification :

factorielle(4) = 4 × factorielle(3)
               = 4 × 3 × factorielle(2)
               = 4 × 3 × 2 × factorielle(1)
               = 4 × 3 × 2 × 1 × factorielle(0)
               = 4 × 3 × 2 × 1 × 1
               = 24

---

Récursif vs Itératif

Toute fonction récursive peut être réécrite de manière itérative (avec des boucles), et inversement.

Comparaison sur l'exemple de la somme

Version récursive :

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

Version itérative :

def somme_iterative(n):
    resultat = 0
    for i in range(1, n + 1):
        resultat += i
    return resultat

Avantages et inconvénients

Critère	Récursif	Itératif
Lisibilité	Souvent plus élégant et proche de la définition mathématique	Peut être plus verbeux
Mémoire	Utilise la pile d'appels (risque de débordement)	Utilise peu de mémoire
Performance	Peut être plus lent (overhead des appels)	Généralement plus rapide
Cas d'usage	Structures récursives (arbres, graphes), diviser pour régner	Calculs simples, itérations

En pratique, on choisit la récursivité quand elle rend le code plus clair ou quand le problème est naturellement récursif (parcours d'arbres, fractales, etc.).

---

Autres types de récursivité

Il existe divers types de récursivité :

• La récursivité simple : un seul appel récursif (comme somme)
• La récursivité multiple : plusieurs appels récursifs dans la fonction
• La récursivité mutuelle : deux fonctions qui s'appellent mutuellement
• La récursivité terminale : l'appel récursif est la dernière opération

Ces différents types de récursivité sont quelque peu différents de ce que l'on vient de voir. Mais nous pourrions les rencontrer dans la suite du programme.

Récursivité multiple : la suite de Fibonacci

À la différence de la récursivité dite simple, il y aura ici plusieurs appels de fonctions dans une même instruction.

En mathématiques, la suite de Fibonacci est une suite de nombres entiers dont chaque terme successif représente la somme des deux termes précédents, et qui commence par 0 puis 1. Ainsi, les dix premiers termes qui la composent sont 0, 1, 1, 2, 3, 5, 8, 13, 21 et 34.

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

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Arbre des appels pour fibonacci(4)

                    fibonacci(4)
                    /          \
            fibonacci(3)      fibonacci(2)
            /        \         /        \
      fibonacci(2)  fibonacci(1)  fibonacci(1)  fibonacci(0)
       /      \          |            |            |
fibonacci(1) fibonacci(0) 1           1            0
     |           |
     1           0

On remarque que fibonacci(2) est calculé deux fois, et fibonacci(1) trois fois. Cette redondance rend l'algorithme très inefficace pour de grandes valeurs de n.

Ce problème sera résolu grâce à la programmation dynamique, que nous verrons dans un prochain chapitre.

---

À retenir

• Une fonction récursive s'appelle elle-même
• Elle doit avoir un cas de base pour s'arrêter
• On prouve la terminaison avec un variant (quantité qui décroît)
• Les appels s'empilent dans la pile d'appels
• Python limite le nombre d'appels récursifs (~1000)
• Récursif ≠ toujours meilleur : choisir selon le problème

---

Auteurs : Florian Mathieu, Timothée Decoster, Enzo Frémeaux

Licence CC BY NC

Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.