Spé. NSI · Terminale · cours rédigé et vérifié par Claryo, conforme au Bulletin officiel
Une fonction est récursive lorsqu'elle s'appelle elle-même dans son propre corps. Pour qu'elle se termine, elle doit impérativement comporter deux ingrédients : un cas de base (une situation simple résolue sans nouvel appel) et un cas récursif qui se ramène à un problème strictement plus petit, convergeant vers le cas de base. Si le cas de base est absent ou jamais atteint, la récursion est infinie et provoque un débordement de la pile d'appels.
Exécuter une fonction récursive met en jeu la pile d'appels. À chaque appel, un cadre contenant les arguments, les variables locales et l'adresse de retour est empilé. Lorsque le cas de base est atteint, les appels se résolvent un à un dans l'ordre inverse : c'est le dépilement. C'est pourquoi une récursion de profondeur n consomme une mémoire O(n), contrairement à une boucle qui peut se contenter d'une mémoire constante.
La récursivité est particulièrement naturelle pour les structures définies récursivement : factorielle (n! = n \times (n-1)!), parcours d'arbres, ou méthode diviser-pour-régner. Elle a néanmoins un coût. L'exemple classique est la suite de Fibonacci : l'implémentation récursive naïve recalcule sans cesse les mêmes valeurs et atteint une complexité exponentielle O(\varphi^{n}). La mémoïsation (mémoriser les résultats déjà calculés) ou une version itérative ramènent à une complexité linéaire O(n).
· Factorielle : n! = n \times (n-1)!, 0! = 1 ; temps O(n), mémoire O(n). · Fibonacci : F_n = F_{n-1} + F_{n-2} ; naïf O(\varphi^{n}), mémoïsé O(n). · Pile d'appels : profondeur = nombre d'appels imbriqués \Rightarrow mémoire O(\text{profondeur}).
Schéma à savoir refaire : l'arbre des appels de factorielle(4) (chaîne linéaire) puis de fibonacci(5) (arbre binaire qui révèle les recalculs).
1) Identifier le cas de base et l'écrire en premier. 2) Écrire le cas récursif sur une donnée plus petite. 3) Vérifier la terminaison (la donnée décroît vers le cas de base). 4) Dérouler la pile d'appels sur un petit exemple pour valider. Pour un palindrome ou un parcours, raccourcir l'entrée à chaque appel (mot[1:-1], sous-arbre, etc.).
· Oublier le cas de base ou écrire un appel récursif qui ne décroît pas : récursion infinie.
· Confondre profondeur de pile et complexité en temps : Fibonacci naïf a une pile O(n) mais un temps O(\varphi^{n}).
· En Python, la profondeur est limitée (~1000) : RecursionError pour les grandes tailles.
· Récursif n'est pas toujours plus efficace : parfois itératif est préférable.
Savoir écrire et dérouler factorielle et somme récursives, expliquer la pile d'appels, et justifier le coût exponentiel de Fibonacci naïf. Pour l'épreuve pratique, maîtriser un parcours récursif (palindrome, somme d'une liste, parcours d'arbre) avec cas de base bien posé.