- À propos de la récursion en Python
- Connaître la limite de récursion avec sys.getrecursionlimit()
- Comprendre pourquoi Python impose une limite de récursion
- Comprendre l'erreur RecursionError
- Modifier la limite avec sys.setrecursionlimit()
- Diminuer la limite de récursion
- Utiliser la récursion avec une condition d'arrêt
- Comprendre les risques d'une limite trop élevée
- Préférer parfois une solution itérative
- À retenir !
1. À propos de la récursion en Python
En programmation, on parle de récursion lorsqu'une fonction s'appelle elle-même, directement ou indirectement. À chaque appel récursif, Python doit conserver des informations permettant de reprendre l'exécution de la fonction lorsque l'appel suivant sera terminé.
Une fonction récursive doit généralement posséder une condition d'arrêt. Sans cette condition, les appels récursifs continueraient jusqu'à atteindre la limite imposée par Python.
Le programme suivant utilise une fonction récursive pour effectuer un compte à rebours.
1 2 3 4 5 6 | def compte(n): print(n) if n > 0: compte(n - 1) compte(5) |
Sortie :
1 2 3 4 5 6 | 5 4 3 2 1 0 |
À chaque appel, la valeur de n diminue. Lorsque n atteint 0, la condition n > 0 devient fausse et aucun nouvel appel récursif n'est effectué.
2. Connaître la limite de récursion avec sys.getrecursionlimit()
Python impose une limite à la profondeur de la récursion. La fonction sys.getrecursionlimit() permet de connaître la valeur actuelle de cette limite.
Le programme suivant affiche la limite de récursion de l'interpréteur Python utilisé.
1 2 3 4 | import sys limite = sys.getrecursionlimit() print("Limite de récursion :", limite) |
Sortie possible :
1 | Limite de récursion : 1000 |
La valeur 1000 est courante dans CPython, mais elle ne doit pas être considérée comme universelle. La valeur peut dépendre de l'implémentation et de la configuration de Python.
Cette limite représente une limite sur la profondeur de la pile de l'interpréteur Python. Elle ne signifie donc pas simplement qu'une fonction donnée peut toujours s'appeler exactement 1000 fois avant de provoquer une erreur.
3. Comprendre pourquoi Python impose une limite de récursion
Lorsqu'une fonction effectue un appel récursif, Python doit conserver le contexte nécessaire aux appels en cours. Une récursion excessivement profonde peut donc utiliser beaucoup de ressources et mettre en danger la stabilité de l'interpréteur.
La limite de récursion constitue ainsi une protection contre une récursion trop profonde.
Le programme suivant affiche les appels successifs d'une petite fonction récursive.
1 2 3 4 5 6 | def afficher(n): print("Appel :", n) if n < 4: afficher(n + 1) afficher(1) |
Sortie :
1 2 3 4 | Appel : 1 Appel : 2 Appel : 3 Appel : 4 |
Avant que l'appel correspondant à 4 ne se termine, les appels correspondant à 1, 2 et 3 sont toujours en attente de leur retour. Une récursion beaucoup plus profonde augmente donc le nombre d'appels actifs.
4. Comprendre l'erreur RecursionError
Lorsqu'une récursion devient trop profonde, Python lève généralement une exception RecursionError. Cette situation apparaît notamment lorsqu'une fonction récursive ne possède pas de condition d'arrêt correcte.
Le programme suivant appelle continuellement la même fonction. L'exception est interceptée afin d'afficher un message simple.
1 2 3 4 5 6 7 | def recommencer(): recommencer() try: recommencer() except RecursionError: print("Erreur : profondeur maximale de récursion dépassée.") |
Sortie :
1 | Erreur : profondeur maximale de récursion dépassée. |
Sans le bloc try...except, Python affiche une trace d'erreur dont le message contient généralement une indication du type maximum recursion depth exceeded.
Une RecursionError ne signifie pas nécessairement qu'il faut augmenter la limite. Elle peut révéler une erreur dans l'algorithme, notamment une condition d'arrêt absente ou incorrecte.
5. Modifier la limite avec sys.setrecursionlimit()
La fonction sys.setrecursionlimit() permet de modifier la limite maximale de profondeur de la pile de l'interpréteur Python. Elle reçoit la nouvelle limite sous forme d'un entier.
Le programme suivant affiche la limite actuelle, la fixe à 2000, puis affiche la nouvelle valeur.
1 2 3 4 5 6 7 | import sys print("Ancienne limite :", sys.getrecursionlimit()) sys.setrecursionlimit(2000) print("Nouvelle limite :", sys.getrecursionlimit()) |
Sortie possible :
1 2 | Ancienne limite : 1000 Nouvelle limite : 2000 |
Après l'appel à sys.setrecursionlimit(2000), la nouvelle limite est utilisée par le processus Python courant.
Il faut cependant éviter d'augmenter cette valeur arbitrairement. Une limite trop élevée peut permettre à la récursion d'atteindre une profondeur dangereuse pour l'interpréteur.
6. Diminuer la limite de récursion
sys.setrecursionlimit() permet également de diminuer la limite. Pour effectuer une démonstration sans perturber la suite du programme, nous pouvons sauvegarder l'ancienne valeur puis la restaurer.
Le programme suivant fixe temporairement la limite à 500.
1 2 3 4 5 6 7 8 9 | import sys ancienne_limite = sys.getrecursionlimit() sys.setrecursionlimit(500) print("Nouvelle limite :", sys.getrecursionlimit()) sys.setrecursionlimit(ancienne_limite) print("Limite restaurée :", sys.getrecursionlimit()) |
Sortie possible :
1 2 | Nouvelle limite : 500 Limite restaurée : 1000 |
Python n'accepte cependant pas n'importe quelle diminution à n'importe quel moment. Si la nouvelle limite demandée est trop basse par rapport à la profondeur d'exécution actuelle, sys.setrecursionlimit() peut lever une RecursionError.
7. Utiliser la récursion avec une condition d'arrêt
Avant de modifier la limite de récursion, il faut vérifier que la fonction récursive possède une condition d'arrêt correcte. Dans de nombreux cas, une récursion normale ne nécessite aucune modification de la limite.
Le calcul de la factorielle fournit un exemple classique. La récursion s'arrête lorsque n atteint 0.
1 2 3 4 5 6 | def factorielle(n): if n == 0: return 1 return n * factorielle(n - 1) print(factorielle(5)) |
Sortie :
1 | 120 |
Les appels peuvent être représentés de manière simplifiée ainsi : factorielle(5) appelle factorielle(4), qui appelle factorielle(3), et ainsi de suite jusqu'à factorielle(0).
Nous pouvons également afficher les différentes valeurs reçues par la fonction pour observer la descente récursive.
1 2 3 4 5 6 7 8 | def factorielle(n): print("n =", n) if n == 0: return 1 return n * factorielle(n - 1) resultat = factorielle(4) print("Résultat :", resultat) |
Sortie :
1 2 3 4 5 6 | n = 4 n = 3 n = 2 n = 1 n = 0 Résultat : 24 |
8. Comprendre les risques d'une limite trop élevée
La fonction sys.setrecursionlimit() doit être utilisée avec prudence. La documentation Python précise qu'une limite trop élevée peut conduire à un plantage de l'interpréteur si la profondeur de récursion devient incompatible avec les ressources disponibles.
Le programme suivant montre comment augmenter modérément la limite sans lancer volontairement une récursion extrêmement profonde.
1 2 3 4 5 6 7 8 | import sys ancienne_limite = sys.getrecursionlimit() sys.setrecursionlimit(1500) print("Limite utilisée :", sys.getrecursionlimit()) sys.setrecursionlimit(ancienne_limite) |
Sortie possible :
1 | Limite utilisée : 1500 |
Il serait en revanche déconseillé de fixer arbitrairement une valeur énorme simplement pour empêcher l'apparition d'une RecursionError.
Avant d'augmenter la limite, il convient donc de vérifier :
- que la récursion possède une condition d'arrêt correcte ;
- que la profondeur importante est réellement nécessaire ;
- qu'une solution itérative ne serait pas plus appropriée ;
- que la nouvelle limite reste raisonnable pour l'environnement utilisé.
9. Préférer parfois une solution itérative
Lorsqu'un algorithme nécessite une très grande profondeur de récursion, il peut être préférable de le transformer en solution itérative. Une boucle évite l'accumulation d'appels récursifs.
Le programme suivant calcule la somme des entiers de 1 à n avec une fonction récursive.
1 2 3 4 5 6 | def somme_recursive(n): if n == 0: return 0 return n + somme_recursive(n - 1) print(somme_recursive(10)) |
Sortie :
1 | 55 |
Le même calcul peut être réalisé avec une boucle for, sans augmenter la profondeur de récursion.
1 2 3 4 5 6 7 | def somme_iterative(n): resultat = 0 for i in range(1, n + 1): resultat = resultat + i return resultat print(somme_iterative(10)) |
Sortie :
1 | 55 |
Les deux fonctions donnent ici le même résultat, mais la version itérative ne dépend pas de la limite de récursion. Pour des profondeurs très importantes, cette approche peut donc être plus adaptée.
10. À retenir !
Python impose une limite de récursion afin de protéger l'interpréteur contre une récursion excessivement profonde. Le module sys fournit deux fonctions principales pour consulter et modifier cette limite.
- sys.getrecursionlimit() retourne la limite actuelle de profondeur de récursion de l'interpréteur.
- Une valeur courante dans CPython est 1000, mais cette valeur n'est pas universelle.
- sys.setrecursionlimit(n) permet de modifier la limite.
- Une récursion trop profonde provoque généralement une RecursionError.
- Une fonction récursive doit posséder une condition d'arrêt correcte.
- Une RecursionError ne signifie pas automatiquement qu'il faut augmenter la limite.
- La limite concerne la profondeur de la pile de l'interpréteur et non simplement un nombre garanti d'appels d'une fonction particulière.
- Une limite trop élevée peut mettre en danger la stabilité de l'interpréteur.
- Il est préférable de ne modifier la limite que lorsqu'une récursion profonde est réellement justifiée.
- Pour certains problèmes, une solution itérative est préférable à une récursion très profonde.
Le programme suivant affiche la limite actuelle, la modifie temporairement puis restaure sa valeur initiale.
1 2 3 4 5 6 7 8 9 10 11 | import sys limite_initiale = sys.getrecursionlimit() print("Limite initiale :", limite_initiale) sys.setrecursionlimit(1500) print("Nouvelle limite :", sys.getrecursionlimit()) sys.setrecursionlimit(limite_initiale) print("Limite restaurée :", sys.getrecursionlimit()) |
Sortie possible :
1 2 3 | Limite initiale : 1000 Nouvelle limite : 1500 Limite restaurée : 1000 |
Auteur : Younes Derfoufi
Lieu de travail : CRMEF OUJDA
Site Web : www.tresfacile.net
Chaine YouTube : https://www.youtube.com/user/InformatiquesFacile
Me contacter : https://www.tresfacile.net/me-contacter/
