Partie 1 : Récursivité¶

Programme officiel (B.O.)¶

B.O. spécial n° 8 du 25 juillet 2019 - NSI Terminale

Contenus	Capacités attendues	Commentaires
Récursivité.	Écrire un programme récursif. Analyser le fonctionnement d'un programme récursif.	Des exemples relevant de domaines variés sont à privilégier.

1. Qu'est-ce que la récursivité ?¶

1.1 Définition¶

Une fonction est dite récursive lorsqu'elle s'appelle elle-même dans sa définition. La récursivité est une technique fondamentale en programmation, qui consiste à résoudre un problème en le décomposant en sous-problèmes plus petits de même nature.

1.2 Structure d'une fonction récursive¶

Toute fonction récursive doit comporter :

Un (ou plusieurs) cas de base : condition d'arrêt, qui renvoie un résultat directement sans appel récursif ;
Un (ou plusieurs) cas récursifs : appel à la fonction elle-même, avec des paramètres plus proches du cas de base.

Sans cas de base

Une fonction récursive sans cas de base s'appelle indéfiniment, provoquant un dépassement de la pile d'appels (RecursionError: maximum recursion depth exceeded).

2. Premiers exemples¶

2.1 Factorielle¶

La factorielle de n (notée n!) est définie par :

\[n! = \begin{cases} 1 & \text{si } n = 0 \\ n \times (n-1)! & \text{si } n \geq 1 \end{cases}\]

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

>>> factorielle(5)
120    # 5 × 4 × 3 × 2 × 1 × 1

2.2 Déroulement de l'exécution¶

factorielle(5)
= 5 × factorielle(4)
= 5 × (4 × factorielle(3))
= 5 × (4 × (3 × factorielle(2)))
= 5 × (4 × (3 × (2 × factorielle(1))))
= 5 × (4 × (3 × (2 × (1 × factorielle(0)))))
= 5 × (4 × (3 × (2 × (1 × 1))))      ← cas de base atteint
= 5 × (4 × (3 × (2 × 1)))             ← remontée
= 5 × (4 × (3 × 2))
= 5 × (4 × 6)
= 5 × 24
= 120

2.3 Puissance¶

\[x^n = \begin{cases} 1 & \text{si } n = 0 \\ x \times x^{n-1} & \text{si } n \geq 1 \end{cases}\]

def puissance(x, n):
    if n == 0:
        return 1
    return x * puissance(x, n - 1)

3. La pile d'appels¶

3.1 Fonctionnement¶

Chaque appel de fonction récursive est empilé dans la pile d'appels (call stack). Quand le cas de base est atteint, les appels sont dépilés un par un, et les résultats remontent.

Pile d'appels pour factorielle(4) :

    ┌─────────────────┐
    │ factorielle(0)  │ ← cas de base → renvoie 1
    ├─────────────────┤
    │ factorielle(1)  │ ← attend factorielle(0) → 1 × 1 = 1
    ├─────────────────┤
    │ factorielle(2)  │ ← attend factorielle(1) → 2 × 1 = 2
    ├─────────────────┤
    │ factorielle(3)  │ ← attend factorielle(2) → 3 × 2 = 6
    ├─────────────────┤
    │ factorielle(4)  │ ← attend factorielle(3) → 4 × 6 = 24
    └─────────────────┘

3.2 Limite de la pile¶

En Python, la profondeur maximale de récursion est par défaut de 1 000 appels. Au-delà, Python lève une erreur RecursionError.

import sys
print(sys.getrecursionlimit())    # 1000 par défaut

4. Exemples variés¶

4.1 Suite de Fibonacci¶

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

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Attention à l'efficacité

Cette version naïve a une complexité exponentielle O(2ⁿ) car elle recalcule les mêmes valeurs de nombreuses fois. Pour n = 40, l'exécution prend plusieurs secondes. On verra en algorithmique comment résoudre ce problème avec la programmation dynamique.

4.2 Somme des chiffres d'un nombre¶

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

>>> somme_chiffres(1234)
10    # 4 + 3 + 2 + 1

4.3 Palindrome¶

def est_palindrome(chaine):
    if len(chaine) <= 1:
        return True
    if chaine[0] != chaine[-1]:
        return False
    return est_palindrome(chaine[1:-1])

>>> est_palindrome("kayak")
True
>>> est_palindrome("python")
False

4.4 Recherche dichotomique récursive¶

def recherche_dicho(tab, val, g=0, d=None):
    if d is None:
        d = len(tab) - 1
    if g > d:
        return -1
    m = (g + d) // 2
    if tab[m] == val:
        return m
    elif tab[m] < val:
        return recherche_dicho(tab, val, m + 1, d)
    else:
        return recherche_dicho(tab, val, g, m - 1)

4.5 Tours de Hanoï¶

Le problème classique des tours de Hanoï consiste à déplacer n disques d'une tige source vers une tige destination, en utilisant une tige intermédiaire, sans jamais poser un grand disque sur un plus petit.

def hanoi(n, source, destination, intermediaire):
    if n == 1:
        print(f"Déplacer disque 1 de {source} vers {destination}")
        return
    hanoi(n - 1, source, intermediaire, destination)
    print(f"Déplacer disque {n} de {source} vers {destination}")
    hanoi(n - 1, intermediaire, destination, source)

>>> hanoi(3, 'A', 'C', 'B')
Déplacer disque 1 de A vers C
Déplacer disque 2 de A vers B
Déplacer disque 1 de C vers B
Déplacer disque 3 de A vers C
Déplacer disque 1 de B vers A
Déplacer disque 2 de B vers C
Déplacer disque 1 de A vers C

Il faut 2ⁿ - 1 déplacements pour résoudre le problème avec n disques.

5. Récursivité vs itération¶

5.1 Comparaison¶

Tout algorithme récursif peut être écrit de manière itérative (avec des boucles), et inversement.

Critère	Récursif	Itératif
Lisibilité	Souvent plus élégant et concis	Parfois plus explicite
Mémoire	Utilise la pile d'appels (risque de dépassement)	Utilise une quantité fixe de mémoire
Adapté à	Structures récursives (arbres, fractales, diviser pour régner)	Boucles simples, parcours séquentiels

5.2 Exemple : factorielle itérative¶

def factorielle_iter(n):
    resultat = 1
    for i in range(1, n + 1):
        resultat *= i
    return resultat

5.3 Quand choisir la récursivité ?¶

La récursivité est particulièrement adaptée quand le problème a une structure naturellement récursive :

arbres (parcours, taille, hauteur) ;
graphes (parcours en profondeur) ;
algorithmes « diviser pour régner » (tri fusion, recherche dichotomique) ;
fractales (flocon de Koch, triangle de Sierpinski).

6. Terminaison d'une fonction récursive¶

Pour prouver qu'une fonction récursive se termine (ne boucle pas indéfiniment), on identifie un variant : une quantité entière positive qui décroît strictement à chaque appel récursif. Quand elle atteint 0 (ou le cas de base), la récursion s'arrête.

Fonction	Variant
`factorielle(n)`	n (décroît de 1 à chaque appel)
`fibonacci(n)`	n (décroît de 1 ou 2)
`recherche_dicho(tab, val, g, d)`	d - g (décroît à chaque appel)
`hanoi(n, ...)`	n (décroît de 1)

À retenir¶

Concept	Description
Récursivité	Fonction qui s'appelle elle-même
Cas de base	Condition d'arrêt (résultat direct, sans appel récursif)
Cas récursif	Appel à soi-même avec des paramètres plus proches du cas de base
Pile d'appels	Empilement des appels en attente, dépilés au retour
Variant	Quantité entière positive qui décroît à chaque appel (preuve de terminaison)
RecursionError	Erreur Python quand la profondeur maximale est dépassée (1 000 par défaut)