Au programme de ce chapitre
- I. Définir une fonction récursive
- II. La pile d'appels
- III. Efficacité : le problème de la récursion multiple
- Savoir-faire
- Exercices types corrigés
- Teste-toi — vrai ou faux ?
- Pièges fréquents et astuces
- À retenir
La définition à retenir
Définition Une fonction est récursive lorsqu'elle s'appelle elle-même dans son propre corps, sur un problème plus petit. Toute fonction récursive correcte doit comporter un cas de base (ou cas d'arrêt), traité directement sans nouvel appel, et un cas récursif, qui rapproche du cas de base à chaque appel.
🔒 Illustration du chapitre completIncluse dans le cours complet, avec la méthode et les exercices corrigés.La voir gratuitement pendant 7 jours
🔒 Illustration du chapitre completIncluse dans le cours complet, avec la méthode et les exercices corrigés.La voir gratuitement pendant 7 jours
Un exemple corrigé
Exemple Testé avec
python3 :
>>> def factorielle(n):
... if n == 0:
... return 1
... return n * factorielle(n - 1)
...
>>> factorielle(6)
720n == 0, qui renvoie 1 sans appel supplémentaire. Le cas récursif ramène le calcul de factorielle(6) à celui de factorielle(5), puis factorielle(4), et ainsi de suite jusqu'à atteindre 0 : c'est bien une suite finie d'appels, garantie par la décroissance stricte de n.Les erreurs fréquentes à éviter
Piège. Oublier le cas de base, ou ne jamais s'en rapprocher, provoque une récursion infinie. Chaque appel doit réduire le problème.
Attention Une fonction récursive sans cas de base atteignable, ou dont le paramètre ne se rapproche jamais du cas de base, provoque une récursion infinie. En pratique, Python interrompt l'exécution avec une erreur
RecursionError dès que la pile d'appels dépasse une profondeur maximale, fixée par défaut à 1000 (valeur renvoyée par sys.getrecursionlimit()).L'astuce du prof
Astuce. Vérifie deux choses : (1) un cas de base atteignable, (2) chaque appel récursif progresse vers ce cas de base.
Exercices corrigés
Cherche d'abord seul, puis ouvre la correction.
Exercice 1
Écris la factorielle n! de façon récursive (en langage courant).
Voir la correction
Cas de base : 0! = 1. Cas récursif : n! = n × (n−1)!. En code :
def f(n): return 1 if n==0 else n*f(n-1).Exercice 2
Pourquoi faut-il toujours un cas de base ?
Voir la correction
Sans cas de base, la fonction s'appelle indéfiniment (récursion infinie → plantage / dépassement de pile).