Cas de base
Situation suffisamment simple pour être résolue directement, sans nouvel appel récursif.
Terminale NSI • Algorithmique • QCM /20
La récursivité
Comprendre comment une fonction peut s’appeler elle-même, suivre la pile des appels et savoir écrire, expliquer et corriger un algorithme récursif.
🔁
1. Qu’est-ce que la récursivité ?
Résoudre un problème en le ramenant à une version plus petite de lui-même
Une fonction est récursive lorsqu’elle s’appelle elle-même, directement ou indirectement. Chaque appel travaille avec ses propres paramètres et variables locales. Pour qu’un algorithme récursif termine, il doit comporter un cas de base et les appels successifs doivent se rapprocher de ce cas.
Cas récursif
La fonction transforme le problème et s’appelle sur une instance plus petite qui doit progresser vers le cas de base.
Les 3 questions à se poser : Quel est le cas de base ? Quel appel récursif est effectué ? Pourquoi cet appel se rapproche-t-il du cas de base ?
2. Exemple classique : la factorielle
n! = n × (n−1) × … × 1 et 0! = 1
La définition mathématique est naturellement récursive : 0! = 1 et, pour n ≥ 1, n! = n × (n−1)!.
def factorielle(n):
if n == 0:
return 1
return n * factorielle(n - 1)Pour factorielle(4), les appels descendent jusqu’au cas de base, puis les résultats remontent :
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
= 243. La pile des appels
Chaque appel doit attendre le résultat du suivant
Lorsqu’une fonction appelle une autre fonction, le contexte de l’appel en cours est conservé dans la pile d’appels (call stack). Chaque appel récursif ajoute un cadre contenant notamment ses paramètres et variables locales. Quand un appel se termine, son cadre est dépilé.
factorielle(4) — attend 4 × …
factorielle(3) — attend 3 × …
factorielle(2) — attend 2 × …
factorielle(1) — attend 1 × …
factorielle(0) → 1
Python limite la profondeur de récursion. Une récursion trop profonde provoque généralement
RecursionError. Une solution récursive correcte mathématiquement n’est donc pas toujours la meilleure implémentation pratique.4. Fibonacci : attention aux appels répétés
Un bon exemple pour comprendre récursivité et complexité
Avec la convention F₀ = 0, F₁ = 1 et Fₙ = Fₙ₋₁ + Fₙ₋₂, une traduction directe donne :
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)Cette version est simple à comprendre mais recalcule plusieurs fois les mêmes valeurs. Par exemple fibonacci(5) calcule fibonacci(3) par plusieurs branches. Son nombre d’appels croît exponentiellement.
Version récursive naïve
Très proche de la définition mathématique, mais beaucoup de sous-problèmes sont recalculés.
Mémoïsation
On mémorise les résultats déjà obtenus. Un sous-problème identique n’est alors pas recalculé, ce qui améliore fortement l’efficacité.
5. Récursif ou itératif ?
Deux manières différentes de décrire certains algorithmes
def factorielle_iterative(n):
resultat = 1
for k in range(2, n + 1):
resultat = resultat * k
return resultatLes deux versions calculent la même fonction. Pour la factorielle, elles effectuent un nombre d’étapes proportionnel à n : O(n). La version récursive utilise toutefois une pile d’appels de profondeur O(n), alors que la version itérative peut fonctionner avec un espace supplémentaire constant.
À retenir : récursif ne signifie ni automatiquement plus rapide, ni automatiquement plus lent. Il faut étudier l’algorithme. La récursivité est particulièrement naturelle pour des structures elles-mêmes récursives, notamment les arbres.
6. Écrire du pseudo-code récursif
Faire apparaître clairement cas de base et réduction du problème
FONCTION somme(n)
SI n = 0 ALORS
RENVOYER 0
SINON
RENVOYER n + somme(n - 1)
FIN SI
FIN FONCTIONPour justifier la terminaison sur un entier naturel n, on remarque que chaque appel remplace n par n−1. La valeur diminue strictement et finit donc par atteindre 0, le cas de base.
7. Les erreurs classiques
Oublier le cas de base
Les appels continuent jusqu’à atteindre la limite de récursion.
Ne pas progresser
f(n) qui rappelle f(n) avec le même argument ne se rapproche pas du cas d’arrêt.
Confondre print et return
Un appel récursif doit généralement renvoyer une valeur exploitable par l’appel précédent.
Oublier le domaine
Une fonction prévue pour n ≥ 0 doit préciser ou contrôler cette précondition.
QCM : récursivité
20 questions • score sur 20