La récursivité
Cours · NSI (terminale), chapitre 5 · terminale, spécialité numérique et sciences informatiques · le début du chapitre, la suite sur Adloun
La récursivité est une technique de programmation fondamentale dans laquelle une fonction s'appelle elle-même pour résoudre un problème. Elle constitue souvent une traduction directe et élégante de définitions mathématiques ou de raisonnements par récurrence. Pour de nombreux problèmes (parcours d'arbres, algorithmes « diviser pour régner », combinatoire), une solution récursive est plus lisible et plus naturelle qu'une solution itérative.
Dans ce chapitre, nous étudions le principe de la récursivité (cas de base et cas récursif), le mécanisme d'exécution à travers la pile d'appels, la question essentielle de la terminaison, ainsi que de nombreux exemples classiques. Nous comparerons enfin l'approche récursive à l'approche itérative et discuterons de ses coûts et de ses limites.
5.1 Principe de la récursivité
5.1.1 Définition et structure d'une fonction récursive
Une fonction est dite récursive lorsqu'elle s'appelle elle-même, directement ou indirectement, au cours de son exécution. La résolution d'un problème est alors ramenée à la résolution d'une ou plusieurs instances plus petites du même problème.
Une fonction récursive correcte est construite autour de deux éléments :
- le cas de base : une (ou plusieurs) situation(s) suffisamment simple(s) pour être résolue(s) directement, sans nouvel appel récursif. Le cas de base arrête la récursion.
- le cas récursif : la fonction se rappelle elle-même sur une instance plus petite du problème, en se rapprochant du cas de base, puis combine le résultat obtenu.
Méthode : Construire une fonction récursive
Pour écrire une fonction récursive, on procède en trois étapes :
- Identifier le cas de base : la plus petite instance, dont la réponse est immédiate.
- Exprimer la solution du problème en fonction de la solution d'une instance plus petite (le cas récursif).
- Vérifier que tout appel récursif se rapproche du cas de base, garantissant ainsi la terminaison.
La factorielle se définit mathématiquement par et pour . Cette définition se traduit directement en code récursif :
def factorielle(n):
if n == 0: # cas de base
return 1
else: # cas recursif
return n * factorielle(n - 1)
print(factorielle(5)) # affiche 120Le cas de base est , le cas récursif appelle factorielle(n - 1), dont l'argument est strictement plus petit.
5.2 La pile d'appels
5.2.1 Mécanisme d'exécution
La pile d'appels (en anglais call stack) est la structure de données qui mémorise, au cours de l'exécution d'un programme, les appels de fonctions en cours. À chaque appel, un enregistrement d'activation (paramètres, variables locales, point de retour) est empilé ; à chaque retour de fonction, il est dépilé. Elle fonctionne selon le principe LIFO (Last In, First Out).
Exercices du chapitre
- Renverser une chaîne corrigé
- Somme des chiffres d'un entier corrigé
- Palindrome récursif corrigé
- Problème — Rendu de monnaie optimal avec reconstruction corrigé
- Puissance entière corrigé
- Longueur d'une liste corrigé