Aller au contenu

Profondeur de récursion⚓︎

Voici une fonction récursive un peu stupide...

🐍 Script Python
def f():
    return f()

Testons-la.

🐍 Console Python
>>> f()
Traceback (most recent call last):
  File "<pyshell>", line 1, in <module>
  File "/home/francky/test.py", line 1, in f
  File "/home/francky/test.py", line 1, in f
  File "/home/francky/test.py", line 1, in f
  [Previous line repeated 996 more times]
  RecursionError: maximum recursion depth exceeded
>>>

On découvre un message d'erreur précédé du Traceback, qui indique quel est le cheminement de l'erreur.

  • La fonction f a appelé 999 fois (3 fois affiché et 996 de plus) la fonction f qui a été appelée depuis le terminal.
  • La fonction f a été appelée récursivement 1000 fois au total.
  • La tentative supplémentaire provoque l'erreur RecursionError: maximum recursion depth exceeded, à savoir : la profondeur maximale de récursion a été dépassée.

Ce fonctionnement est normal.

  • Il évite aux débutants de ralentir fortement un ordinateur avec un programme qui utiliserait toute sa mémoire.

Hors programme en NSI

Il est possible de modifier la limite de profondeur de récursion, si le besoin est réel.

🐍 Script Python
import sys
sys.setrecursionlimit(10**5)

La limite est désormais à \(10^5\).

Sur France-IOI, il peut être utile de savoir cela.