NSI · Terminale
Terminaison et synthèse de la récursivité
Prouver la terminaison d'une fonction récursive avec un variant de récursion et synthèse des concepts essentiels.
Terminaison & Synthèse de la Récursivité
Dans ce chapitre, nous abordons la preuve formelle de terminaison d'un algorithme récursif ainsi que la synthèse complète des notions indispensables du cours.
1. Preuve de Terminaison : Le Variant de Récursion
Lorsqu'on conçoit une fonction récursive, il est indispensable de prouver formellement qu'elle ne provoquera pas une récursion infinie (RecursionError).
Notion de Variant de Récursion
Un variant de récursion (ou variant de boucle) est une grandeur entière positive v associée aux paramètres de la fonction telle que :
- Positivité : v ≥ 0 pour tous les appels valides.
- Décroissance stricte : À chaque nouvel appel récursif, la valeur de v diminue strictement d'au moins 1 (vₖ₊₁ < vₖ).
Puisqu'une suite d'entiers naturels strictement décroissante est obligatoirement finie, la condition d'arrêt (le cas de base) sera nécessairement atteinte après un nombre fini d'appels.
Exemples classiques de variants :
- Calcul de n! : Le variant est v(n) = n. À chaque appel, n diminue strictement de 1 jusqu'à atteindre 0.
- Calcul de aⁿ : Le variant est l'exposant n. Il diminue strictement à chaque étape jusqu'à n = 0.
- Somme des entiers de a à b : Le variant est la différence v(a, b) = b - a. À chaque appel
somme(a + 1, b), b - a diminue de 1 jusqu'à 0 (lorsque a = b).
2. Synthèse : Les Incontournables de la Récursivité
Ce qu'il faut absolument retenir
- Définition : Une fonction récursive est une fonction qui s'appelle elle-même pour résoudre une instance simplifiée du même problème.
- Cas de Base : Condition d'arrêt obligatoire sans nouvel appel récursif, qui renvoie une valeur terminale.
- Cas Récursif : Branche où la fonction s'appelle avec un paramètre strictement plus proche du cas de base.
- Pile d'exécution : Les cadres d'appels s'empilent (Push) lors de la descente et se dépilent (Pop) lors de la remontée des valeurs calculées.
- Portée locale : Chaque appel possède son propre environnement de variables indépendant dans la pile.
- Preuve de terminaison : On exhibe un variant entier strictement décroissant et minoré pour garantir l'arrêt.
Avez-vous compris et assimilé ce cours ?
+50 XPÉtudiez le contenu activement pendant au moins 45 secondes pour pouvoir débloquer la validation au mérite.