Correction et terminaison (Bac 🎯)⚓︎

Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.

programme

Sources et crédits pour ce cours

Pour préparer ce cours, j'ai utilisé :

le cours d'Olivier Lécluse
le manuel NSI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen
le manuel NSI chez Hachette sous la direction de Michel Beaudouin Lafon
la ressource Eduscol sur la récursivité
le cour e-nsi sur la récursivité
le cours de mon collègue Pierre Duclosson

🔖 Synthèse de ce qu'il faut retenir pour le bac

Étude de cas⚓︎

Exercice 3

🎯 Analyser le fonctionnement d'un programme récursif

ÉnoncéCorrection

On veut compléter la fonction récursive puissance_rec dans l'IDE ci-dessous pour que puissance_rec(x, n) renvoie la valeur \(x^{n}\) sans utiliser l'opérateur d'exponentiation ** de Python.

a. Déterminer un cas de base.

b. Comment peut-on déterminer puissance_rec(x, n) à partir de puissance_rec(x, n - 1) (réduction) ?

c. Compléter le code.

###

# --- HDR ---#bksl-nlDICOpy-undTRACE = dict()bksl-nlbksl-nlbksl-nldef trace(f):bksl-nl """Remplace une fonction f par une fonction enrobante g."""bksl-nlbksl-nl def g(py-strargs):bksl-nl """Fonction enrobante (wraped en anglais)."""bksl-nl arguments = f"{args[0]}"bksl-nlbksl-nl if g.tracepy-undpile:bksl-nl g.pile.append(f"Contexte de {g.py-undpy-undnamepy-undpy-und}{tuple(e for e in args)}")bksl-nl lmax = max([len(contexte) for contexte in g.pile])bksl-nl print(f"Appel de {g.py-undpy-undnamepy-undpy-und}({arguments}) => descente \n")bksl-nl print("État de la pile : \n")bksl-nl for contexte in g.pile[::-1]:bksl-nl print("|{0:^{1}}|".format(contexte, lmax))bksl-nl print(f"|{lmax py-str '-'}|")bksl-nl print("\n" py-str 3)bksl-nl if not (g.tracepy-undpile) and g.trace:bksl-nl print(bksl-nl "| " py-str (g.indentation - 1)bksl-nl + "┌"bksl-nl + f"Appel de {g.py-undpy-undnamepy-undpy-und}({arguments}) => descente"bksl-nl )bksl-nl g.indentation += 1bksl-nl g.py-undpy-unddictpy-undpy-und["indentation"] = g.indentationbksl-nl retour = f(py-strargs)bksl-nl if not (g.tracepy-undpile) and g.trace:bksl-nl g.indentation -= 1bksl-nl g.py-undpy-unddictpy-undpy-und["indentation"] = g.indentationbksl-nl print(bksl-nl "| " py-str (g.indentation - 1)bksl-nl + "└"bksl-nl + f"Fin de {g.py-undpy-undnamepy-undpy-und}({arguments}) <= remontée"bksl-nl )bksl-nl if g.tracepy-undpile:bksl-nl print(f"Fin de {g.py-undpy-undnamepy-undpy-und}({arguments}) <= remontée \n")bksl-nl lmax = max([len(contexte) for contexte in g.pile])bksl-nl print("État de la pile : \n")bksl-nl for contexte in g.pile[::-1]:bksl-nl print("|{0:^{1}}|".format(contexte, lmax))bksl-nl print(f"|{lmax py-str '-'}|")bksl-nl print("\n" py-str 2)bksl-nl g.pile.pop()bksl-nl return retourbksl-nlbksl-nl # on vérifie si le nom de f apparaît déjà dans table des fonctions tracéesbksl-nl if f.py-undpy-undnamepy-undpy-und not in DICOpy-undTRACE:bksl-nl g.py-undpy-undnamepy-undpy-und = f.py-undpy-undnamepy-undpy-und # g portera le même que fbksl-nl g.indentation = 1 # compteur d'indentation attaché à gbksl-nl g.trace = True # booléen pour activer ou désactiver la tracebksl-nl g.tracepy-undpile = Falsebksl-nl g.pile = []bksl-nl DICOpy-undTRACE[f.py-undpy-undnamepy-undpy-und] = gbksl-nl return DICOpy-undTRACE[f.py-undpy-undnamepy-undpy-und]bksl-nlbksl-nlbksl-nldef desactiverpy-undtrace(fonction):bksl-nl if fonction.py-undpy-undnamepy-undpy-und in DICOpy-undTRACE:bksl-nl del DICOpy-undTRACE[fonction.py-undpy-undnamepy-undpy-und]bksl-nl fonction.trace = Falsebksl-nlbksl-nlbksl-nldef activerpy-undtracepy-undpile(fonction):bksl-nl if fonction.py-undpy-undnamepy-undpy-und in DICOpy-undTRACE:bksl-nl fonction.tracepy-undpile = Truebksl-nlbksl-nlbksl-nldef desactiverpy-undtracepy-undpile(fonction):bksl-nl if fonction.py-undpy-undnamepy-undpy-und in DICOpy-undTRACE:bksl-nl fonction.tracepy-undpile = Falsebksl-nlbksl-nlbksl-nl# --- HDR ---#bksl-nlbksl-nldef puissancepy-undrec(x, n):bksl-nl """bksl-nl Renvoie x py-strpy-str n sans utiliser l'opérateur py-strpy-strbksl-nl Fonction récursive bksl-nlbksl-nl Paramètres:bksl-nl x (int): entier xbksl-nl n (int): exposant >= 0bksl-nl """bksl-nl # à compléterbksl-nl bksl-nldef testpy-undpuissancepy-undrec(x, n):bksl-nl assert puissancepy-undrec(2, 0) == 1, "échec sur puissancepy-undrec(2, 0)"bksl-nl assert puissancepy-undrec(2, 1) == 2, "échec sur puissancepy-undrec(2, 1)"bksl-nl assert puissancepy-undrec(2, 2) == 4, "échec sur puissancepy-undrec(2, 2)"bksl-nl assert puissancepy-undrec(2, 3) == 8, "échec sur puissancepy-undrec(2, 3)"bksl-nl assert puissancepy-undrec(3, 2) == 9, "échec sur puissancepy-undrec(3, 2)"bksl-nl assert puissancepy-undrec(17, 9) == 118587876497, "échec sur puissancepy-undrec(17, 9) == 118587876497"bksl-nl

On va démontrer la correction de la fonction puissance_rec, c'est-à-dire que la propriété \(P(n): puissance\_rec(x, n) = x^{n}\) est vraie pour tout entier naturel \(n\) positif.
Méthode 2 : preuve de correction par récurrence

La correction d'une fonction récursive se démontre à l'aide d'un raisonnement par récurrence comme en Mathématiques :
- Initialisation : on démontre que la propriété est vraie pour le ou les cas de base (sans en oublier), ici pour \(n=0\).
- Hérédité : on démontre que pour tout entier naturel \(n\), si on suppose que \(P(n)\) est vraie alors \(P(n+1)\) est encore vraie.
Appliquez le raisonnement par récurrence pour démontrer que \(P(n)\) est vraie pour tout entier naturel \(n\) et donc que la fonction puissance_rec est correcte.
On a vu dans l'exercice 1 que comme pour un algorithme itératif avec une boucle non bornée, il est possible qu'un algorithme récursif ne se termine pas.

Déplier et lire le paragraphe suivant puis justifier que puissance_rec se termine.
Récursivité et terminaison

Une fonction récursive ne se termine pas si les étapes de réduction ne font pas converger les appels récursifs vers un cas de base.

Dans l'exercice 1, on a vu que celà peut se produire :
- Si la fonction ne propose pas de cas de base :
🐍 Script Python
```
def factorielle(n):
    """Fausse"""
    # réduction mais pas de cas de base
    return n * factorielle(n-1)
```
- Si la fonction implémentée est appelée sur une valeur en dehors du domaine de définition de l'algorithme récursif :
🐍 Script Python
```
def factorielle(n):
    """Renvoie n! = 1 *2 * ... (n-1) * n pour tout entier n >= 0"""
    # cas de base
    if n == 0:
        return 1
    # réduction 
    return n * factorielle(n-1)

# Appel sur un nombre négatif => descente infinie
factorielle(-1)
```
On peut prévenir ces problèmes en vérifiant des préconditions (programmation défensive).
🐍 Script Python
```
def factorielle(n):
    """Renvoie n! = 1 *2 * ... (n-1) * n pour tout entier n >= 0"""
    assert isinstance(n, int) and n >= 0
    # cas de base
    if n == 0:
        return 1
    # réduction 
    return n * factorielle(n-1)

# Appel sur un nombre négatif => descente infinie
factorielle(-1)
```
- Si dans la fonction implémentée, la réduction ne fait pas converger les appels récursifs vers un cas de base. Par exemple dans le cas ci-dessous l'appel factorielle(1) ne se termine pas car factorielle(1) appelle factorielle(-1) qui appelle factorielle(-3) etc ... Donc le cas de base 0 a été sauté et ne sera jamais atteint.
🐍 Script Python
```
def factorielle(n):
    """Fausse"""
    # cas de base
    if n == 0:
        return 1
    # réduction fausse
    return n * factorielle(n - 2)
```
💡 Comme pour une boucle, on peut démontrer que fonction récursive se termine, à l'aide d'un variant, une quantité entière positive dont on démontre qu'elle décroît lors de chaque appel récursif jusqu'à ce que le cas de base soit atteint.

Au tableau ...