Comment justifier qu’une fonction récursive termine ?
Réponse courte
Pour montrer qu’une fonction récursive termine, précise ses entrées et établis qu’une quantité entière naturelle diminue strictement jusqu’à un cas de base.
Comprendre
Chercher un variant
Pour justifier la terminaison, identifie une quantité associée à chaque appel, entière, naturelle et strictement décroissante lors de chaque appel récursif. On l’appelle un variant. Une suite de naturels ne peut pas diminuer strictement indéfiniment : la diminution doit donc s’arrêter, à condition que l’arrêt corresponde à un cas de base.
Appliquer la démarche à somme(n)
Supposons que somme(n) calcule la somme de 1 à n pour n entier naturel, avec somme(0)=0 et somme(n)=n+somme(n−1) si n>0. Le variant est n. Pour n positif, l’appel suivant reçoit n−1, qui reste naturel et est strictement inférieur à n. En répétant, on atteint zéro ; le cas de base renvoie alors une valeur sans nouvel appel. La fonction termine donc pour toute entrée de ce domaine.
La preuve dépend du contrat d’entrée. Pour n négatif, la même réduction ne va pas vers zéro et le raisonnement ne s’applique pas. Un test conditionnel visible ne suffit pas : il faut établir que le chemin d’exécution depuis toute entrée autorisée rejoint une base. La terminaison ne prouve pas, à elle seule, que la valeur renvoyée est correcte.
Étapes
- Énonce les entrées admises par la fonction.
- Repère une quantité naturelle calculée à partir de l’argument ou de l’état du problème.
- Montre que chaque appel récursif la diminue strictement tout en restant dans le domaine.
- Montre que cette diminution conduit à un cas de base qui n’effectue pas de nouvel appel.
Exemples
- Dans somme(n), avec n naturel, le variant n devient n−1 à chaque appel et finit par atteindre 0.
- Dans palindrome(texte), la longueur de la chaîne diminue de deux à chaque appel ; elle atteint 0 ou 1 si chaque comparaison des extrémités conduit à l’appel intérieur.
- Si une fonction rappelle somme(n) avec le même n positif, le variant ne diminue pas et le cas somme(0) n’est jamais atteint.
Pièges fréquents
- S’appuyer uniquement sur la présence d’un if : une branche récursive peut se rappeler sans jamais atteindre la condition d’arrêt.
- Confondre terminaison et correction : le variant justifie l’arrêt, mais il faut un autre raisonnement pour montrer que la valeur renvoyée est juste.
