Programmation Python et récursivité · NSI Terminale (spé maths)

Spécifier, tester, sécuriser une fonction

Une fonction est un contrat : on indique ce qu'elle reçoit (les préconditions) et ce qu'elle renvoie (la postcondition). Ce contrat est la spécification. Un code qui marche « sur un exemple » n'est pas pour autant correct.

def maximum(tab):

    """Renvoie le plus grand élément de tab (liste non vide d'entiers)."""

    m = tab[0]

    for x in tab:

        if x > m:

            m = x

    return m

Remarque l'initialisation m = tab[0] : on part d'un élément de la liste, pas d'une valeur arbitraire comme 0.

Pour détecter ce genre de bug, on construit un jeu de tests qui couvre :

un cas courant ([3, 8, 2]) ;
les cas limites (un seul élément, tous égaux) ;
les cas « pièges » (que des nombres négatifs, le maximum en première ou en dernière position).

On automatise les vérifications avec assert :

assert maximum([3, 8, 2]) == 8

assert maximum([-5, -2, -9]) == -2

assert maximum([4]) == 4

Si une assertion est fausse, Python lève une AssertionError et indique la ligne : le bug est repéré tout de suite.

On peut aussi utiliser assert dans une fonction pour vérifier une précondition :

def racine_entiere(n):

    assert n >= 0, "n doit être positif ou nul"

    ...

Entraîne-toi★☆☆

On souhaite écrire une fonction maximum(tab) qui renvoie le plus grand élément d'une liste non vide tab de nombres entiers. Un élève propose le code suivant. 1. Donner…

On souhaite écrire une fonction maximum(tab) qui renvoie le plus grand élément d'une liste non vide tab de nombres entiers. Un élève propose le code suivant.

def maximum(tab):

    m = 0

    for x in tab:

        if x > m:

            m = x

    return m

Donner la valeur renvoyée par maximum([3, 8, 2]).
Donner la valeur renvoyée par maximum([-5, -2, -9]). Expliquer pourquoi cette valeur ne correspond pas à la spécification de la fonction.
Corriger la fonction pour qu'elle soit conforme à sa spécification.
Proposer un jeu de trois tests, dont un avec uniquement des nombres négatifs, qui permet de détecter l'erreur initiale.

Résoudre

Écrire une fonction récursive

Une fonction est récursive si elle s'appelle elle-même. Pour qu'elle soit correcte, il faut toujours :

un cas de base : une situation où elle renvoie le résultat sans nouvel appel ;
un cas récursif : elle se ramène à un problème plus petit du même type ;
une terminaison : une quantité entière positive qui décroît strictement à chaque appel, donc qui finit par atteindre le cas de base.

def puissance(x, n):

    if n == 0:

        return 1

    else:

        return x * puissance(x, n - 1)

Ici, le cas de base est n == 0. Le cas récursif utilise $x^n = x \times x^{n-1}$. La quantité qui décroît est n, entier naturel : il ne peut pas décroître indéfiniment.

Dérouler les appels de somme_chiffres(2548)

On considère :

def somme_chiffres(n):

    if n < 10:

        return n

    else:

        return n % 10 + somme_chiffres(n // 10)

Rappel : n % 10 est le chiffre des unités, n // 10 est le nombre privé de son dernier chiffre.

On descend : somme_chiffres(2548) renvoie 8 + somme_chiffres(254), puis 4 + somme_chiffres(25), puis 5 + somme_chiffres(2).

Cas de base : somme_chiffres(2) renvoie 2, car $2 < 10$.

On remonte : 5 + 2 = 7, puis 4 + 7 = 11, puis 8 + 11 = 19. Le résultat est 19.

Terminaison : n // 10 est un entier naturel strictement plus petit que n dès que n ≥ 10. La suite des arguments décroît strictement et finit par passer sous 10.

Même démarche pour somme_chiffres(7 031). Écris les appels successifs, puis la valeur renvoyée.

Chaque appel non terminé est mis en attente dans la pile d'appels. Une récursion sans cas de base (ou qui ne s'en approche pas) remplit la pile jusqu'à une RecursionError (profondeur maximale dépassée, 1 000 par défaut en Python).

La récursivité fonctionne aussi sur les chaînes et les listes, avec des tranches :

def est_palindrome(s):

    if len(s) <= 1:

        return True

    elif s[0] != s[-1]:

        return False

    else:

        return est_palindrome(s[1:-1])

Ici, len(s) décroît d'au moins 2 à chaque appel : c'est la quantité qui décroît strictement.

Entraîne-toi★☆☆

On considère la fonction suivante, qui prend en paramètre un entier naturel n. 1. Donner la valeur de 2 548 % 10 et celle de 2 548 // 10. 2. Détailler les appels…

On considère la fonction suivante, qui prend en paramètre un entier naturel n.

def somme_chiffres(n):

    if n < 10:

        return n

    else:

        return n % 10 + somme_chiffres(n // 10)

Donner la valeur de 2 548 % 10 et celle de 2 548 // 10.
Détailler les appels successifs effectués par somme_chiffres(2548), puis donner la valeur renvoyée.
Justifier que l'exécution de somme_chiffres(n) se termine pour tout entier naturel n.

Résoudre

Entraîne-toi★☆☆

On considère la fonction récursive suivante. 1. Donner la valeur renvoyée par puissance(3, 4). 2. Indiquer le nombre total d'appels de la fonction puissance effectués…

On considère la fonction récursive suivante.

def puissance(x, n):

    if n == 0:

        return 1

    else:

        return x * puissance(x, n - 1)

Donner la valeur renvoyée par puissance(3, 4).
Indiquer le nombre total d'appels de la fonction puissance effectués lors de l'exécution de puissance(3, 4), appel initial compris.
Expliquer ce qui se produit lors de l'exécution de puissance(2, -1).
Écrire une assertion à placer au début de la fonction pour se prémunir contre ce problème.

Résoudre

Entraîne-toi★★☆

On considère la fonction suivante, qui prend en paramètre une chaîne de caractères s. 1. Donner la valeur renvoyée par est_palindrome("radar") et préciser le nombre…

On considère la fonction suivante, qui prend en paramètre une chaîne de caractères s.

def est_palindrome(s):

    if len(s) <= 1:

        return True

    elif s[0] != s[-1]:

        return False

    else:

        return est_palindrome(s[1:-1])

Donner la valeur renvoyée par est_palindrome("radar") et préciser le nombre d'appels de la fonction effectués, appel initial compris.
Donner la valeur renvoyée par est_palindrome("lycee") et préciser le nombre d'appels effectués.
Identifier le cas de base et le cas récursif, puis justifier la terminaison en précisant la quantité qui décroît strictement à chaque appel.
Écrire une fonction récursive compte(s, c) qui renvoie le nombre d'occurrences du caractère c dans la chaîne s.

Résoudre

Compter les appels : coût d'une récursion

Une fonction récursive peut s'appeler plusieurs fois à chaque exécution. Le nombre d'appels peut alors exploser. C'est le cas de la suite de Fibonacci :

def fib(n):

    if n <= 1:

        return n

    else:

        return fib(n - 1) + fib(n - 2)

Voici l'arbre des appels de fib(4) :

Tu vois que fib(2) est calculé deux fois : on refait des calculs déjà faits. Si $C(n)$ est le nombre d'appels, alors $C(n) = 1 + C(n-1) + C(n-2)$ (l'appel initial plus les deux sous-arbres). Ce nombre croît à peu près comme $F_n$ lui-même, c'est-à-dire de façon exponentielle.

Remède : la mémoïsation. On garde en mémoire les résultats déjà calculés dans un dictionnaire.

def fib_memo(n, memo=None):

    if memo is None:

        memo = {}

    if n in memo:

        return memo[n]

    if n <= 1:

        resultat = n

    else:

        resultat = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)

    memo[n] = resultat

    return resultat

Chaque valeur n'est calculée qu'une fois : le nombre d'appels devient proportionnel à $n$.

Démontrer une propriété par récurrence

Pour établir une formule sur le nombre d'opérations, on utilise le raisonnement par récurrence (initialisation, hérédité, conclusion).

Tours de Hanoï : combien de déplacements ?

Le programme suivant déplace n disques de dep vers arr :

def hanoi(n, dep, arr, aux):

    if n > 0:

        hanoi(n - 1, dep, aux, arr)

        print(dep, "->", arr)

        hanoi(n - 1, aux, arr, dep)

On note $h(n)$ le nombre de déplacements affichés. Montrons que $h(n) = 2^n - 1$.

Relation de récurrence : l'appel affiche $h(n-1)$ déplacements, un déplacement, puis encore $h(n-1)$ déplacements. Donc $h(n) = 2h(n-1) + 1$ pour $n \geqslant 1$, et $h(0) = 0$ (aucun affichage).

Initialisation : $2^0 - 1 = 0 = h(0)$. La propriété est vraie au rang 0.

Hérédité : on suppose $h(k) = 2^k - 1$ pour un entier $k \geqslant 0$. Alors $h(k+1) = 2h(k) + 1 = 2(2^k - 1) + 1 = 2^{k+1} - 1$.

Conclusion : pour tout entier $n \geqslant 0$, $h(n) = 2^n - 1$. Avec 64 disques, il faudrait $2^{64} - 1$ déplacements : le coût est exponentiel.

Pour $n = 3$, combien de déplacements ? Vérifie avec la relation $h(n) = 2h(n-1) + 1$, puis avec la formule.

Entraîne-toi★★★

On considère la fonction de Fibonacci définie par $F_0 = 0$, $F_1 = 1$ et $F_n = F_{n-1} + F_{n-2}$ pour $n \geqslant 2$. On note $C(n)$ le nombre total d'appels de la…

On considère la fonction de Fibonacci définie par $F_0 = 0$, $F_1 = 1$ et $F_n = F_{n-1} + F_{n-2}$ pour $n \geqslant 2$.

def fib(n):

    if n <= 1:

        return n

    else:

        return fib(n - 1) + fib(n - 2)

On note $C(n)$ le nombre total d'appels de la fonction fib (appel initial compris) lors de l'exécution de fib(n).

Donner $C(0)$, $C(1)$, puis justifier que $C(n) = 1 + C(n-1) + C(n-2)$ pour $n \geqslant 2$.
Calculer $C(2)$, $C(3)$, $C(4)$ et $C(5)$.
Montrer par récurrence que, pour tout entier $n \geqslant 0$, $C(n) = 2F_{n+1} - 1$.
On propose la version suivante.

def fib_memo(n, memo=None):

    if memo is None:

        memo = {}

    if n in memo:

        return memo[n]

    if n <= 1:

        resultat = n

    else:

        resultat = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)

    memo[n] = resultat

    return resultat

a) Expliquer le rôle du dictionnaire `memo`.

b) Expliquer pourquoi le nombre de calculs effectifs de la valeur $F_k$ est au plus égal à 1 pour chaque $k$ compris entre 0 et $n$.

Résoudre

Entraîne-toi★★★

Le problème des tours de Hanoï consiste à déplacer $n$ disques de tailles différentes d'une tige de départ vers une tige d'arrivée, en utilisant une tige auxiliaire. On…

Le problème des tours de Hanoï consiste à déplacer $n$ disques de tailles différentes d'une tige de départ vers une tige d'arrivée, en utilisant une tige auxiliaire. On déplace un seul disque à la fois et on ne pose jamais un disque sur un disque plus petit. Les disques sont initialement empilés par taille décroissante sur la tige de départ.

def hanoi(n, dep, arr, aux):

    if n > 0:

        hanoi(n - 1, dep, aux, arr)

        print(dep, "->", arr)

        hanoi(n - 1, aux, arr, dep)

Donner les affichages successifs produits par l'appel hanoi(2, "A", "C", "B").
On note $h(n)$ le nombre de déplacements de disques effectués par hanoi(n, ...). Justifier que $h(0) = 0$ et que $h(n) = 2\,h(n-1) + 1$ pour $n \geqslant 1$.
Montrer par récurrence que $h(n) = 2^n - 1$ pour tout entier $n \geqslant 0$.
Calculer $h(3)$ et $h(10)$.
Un affichage prend 1 ms. Calculer, en secondes, la durée nécessaire pour $n = 20$ disques, puis la comparer à la durée nécessaire pour $n = 10$. Conclure sur la croissance du coût de cet algorithme.

Résoudre

Diviser pour régner : le tri fusion

Le principe « diviser pour régner » se décompose en trois temps :

diviser le problème en sous-problèmes plus petits ;
résoudre chaque sous-problème (souvent récursivement) ;
combiner les solutions.

Pour le tri fusion, on coupe la liste en deux, on trie chaque moitié, puis on fusionne les deux listes triées.

def tri_fusion(tab):

    if len(tab) <= 1:

        return tab

    milieu = len(tab) // 2

    gauche = tri_fusion(tab[:milieu])

    droite = tri_fusion(tab[milieu:])

    return fusion(gauche, droite)

Exemple sur [8, 3, 5, 1] :

La fusion parcourt simultanément les deux listes triées. À chaque étape, on compare les deux premiers éléments non encore utilisés et on place le plus petit dans la liste résultat.

def fusion(l1, l2):

    res = []

    i, j = 0, 0

    while i < len(l1) and j < len(l2):

        if l1[i] <= l2[j]:

            res.append(l1[i])

            i = i + 1

        else:

            res.append(l2[j])

            j = j + 1

    return res + l1[i:] + l2[j:]

Coût. Une liste de $n$ éléments est coupée environ $\log_2 n$ fois (on divise par 2 jusqu'à 1). À chaque niveau, les fusions parcourent au total $n$ éléments. Le coût est donc de l'ordre de $n \log_2 n$, nettement meilleur que $n^2$ pour un tri naïf (par insertion ou sélection).

Entraîne-toi★★☆

On étudie le tri fusion d'une liste de nombres selon le principe « diviser pour régner ». On rappelle que la fonction fusion prend en paramètres deux listes triées par…

On étudie le tri fusion d'une liste de nombres selon le principe « diviser pour régner ». On rappelle que la fonction fusion prend en paramètres deux listes triées par ordre croissant et renvoie une liste triée contenant tous leurs éléments.

def tri_fusion(tab):

    if len(tab) <= 1:

        return tab

    milieu = len(tab) // 2

    gauche = tri_fusion(tab[:milieu])

    droite = tri_fusion(tab[milieu:])

    return fusion(gauche, droite)

Donner le résultat de fusion([1, 4, 7], [2, 3, 9]).
Écrire la fonction fusion(l1, l2), sans utiliser de fonction de tri prédéfinie.
Représenter les découpages successifs effectués par tri_fusion([6, 2, 9, 4, 1, 7, 3, 8]). Donner le nombre de niveaux de découpage jusqu'aux listes de longueur 1.
Pour une liste de longueur $n = 1\,024$, donner le nombre de niveaux de découpage, puis l'ordre de grandeur $n \log_2 n$ du nombre total d'opérations élémentaires (comparaisons) effectuées lors des fusions.

Résoudre

Programmation dynamique : le rendu de monnaie

Quand un problème se ramène à des sous-problèmes qui se recoupent (comme fib), on utilise la programmation dynamique : on calcule les solutions des petits sous-problèmes une seule fois, on les stocke, et on s'en sert pour les plus grands.

Problème : rendre la somme s avec le moins de pièces possible. Avec les pièces 1, 5 et 6 centimes, rendons 10 centimes.

L'algorithme glouton prend à chaque fois la plus grande pièce possible : 6 + 1 + 1 + 1 + 1, soit 5 pièces. Or 5 + 5 n'utilise que 2 pièces : le glouton n'est pas toujours optimal.

La programmation dynamique, elle, donne toujours la solution optimale. On note $m(s)$ le nombre minimal de pièces pour rendre $s$. Alors $m(0) = 0$ et, pour $s \geqslant 1$,

$$m(s) = 1 + \min \{ m(s - p) \ ;\ p \text{ pièce},\ p \leqslant s \}.$$

Pourquoi ? La dernière pièce rendue vaut forcément l'une des valeurs $p$, et il reste alors $s - p$ à rendre de façon optimale.

En Python, on remplit un tableau de bas en haut :

def rendu_dyn(s, pieces):

    m = [0] * (s + 1)

    for v in range(1, s + 1):

        meilleur = v          # borne : v pièces de 1 (si 1 est une pièce)

        for p in pieces:

            if p <= v and m[v - p] + 1 < meilleur:

                meilleur = m[v - p] + 1

        m[v] = meilleur

    return m[s]

Entraîne-toi★★☆

Un automate de rendu de monnaie dispose de pièces de valeurs 1, 3 et 4 (en centimes d'euro), en quantité illimitée. On cherche à rendre une somme s avec un nombre…

Un automate de rendu de monnaie dispose de pièces de valeurs 1, 3 et 4 (en centimes d'euro), en quantité illimitée. On cherche à rendre une somme s avec un nombre minimal de pièces.

On considère l'algorithme glouton suivant.

def rendu_glouton(s, pieces):

    #pieces est triée par ordre décroissant

    nb = 0

    for p in pieces:

        nb = nb + s // p

        s = s % p

    return nb

Donner la valeur de rendu_glouton(6, [4, 3, 1]). Montrer que ce résultat n'est pas optimal.
On note $m(s)$ le nombre minimal de pièces nécessaires pour rendre la somme $s$. On a $m(0) = 0$ et, pour $s \geqslant 1$, $m(s) = 1 + \min m(s - p)$, le minimum étant pris sur les pièces $p$ telles que $p \leqslant s$. Calculer $m(s)$ pour $s$ allant de 0 à 6.
Écrire une fonction rendu_dyn(s, pieces) qui renvoie le nombre minimal de pièces en construisant une liste m telle que m[i] contienne $m(i)$ pour $0 \leqslant i \leqslant s$.
Expliquer en quoi cette méthode relève de la programmation dynamique.

Résoudre

Un programme est une donnée : le problème de l'arrêt

En Python, une fonction peut être passée en argument d'une autre fonction : un programme est lui-même une donnée. On peut donc écrire un programme qui en analyse un autre. Peut-on écrire un programme qui, pour n'importe quel programme f et n'importe quelle donnée x, décide si f(x) se termine ? C'est le problème de l'arrêt.

Réponse : non. Ce problème est indécidable (Alan Turing, 1936). La démonstration utilise un raisonnement par l'absurde :

On suppose qu'il existe une fonction arrete(f, x) qui se termine toujours et renvoie True si f(x) se termine, False sinon.
On construit à partir d'elle une fonction paradoxe qui fait le contraire de ce que arrete prédit pour elle-même : elle boucle si arrete annonce qu'elle s'arrête, et s'arrête si arrete annonce qu'elle boucle.
On examine paradoxe(paradoxe) : dans les deux cas possibles, on obtient une contradiction.
L'hypothèse de départ est donc fausse : arrete ne peut pas exister.

Entraîne-toi★★★

On suppose qu'il existe une fonction arrete(f, x) qui prend en paramètres une fonction Python f et une donnée x, et qui renvoie True si l'appel f(x) se termine, et False…

On suppose qu'il existe une fonction arrete(f, x) qui prend en paramètres une fonction Python f et une donnée x, et qui renvoie True si l'appel f(x) se termine, et False s'il ne se termine jamais. On suppose que arrete se termine toujours.

On définit la fonction suivante.

def paradoxe(f):

    if arrete(f, f):

        while True:

            pass

    else:

        return 0

Expliquer ce que fait paradoxe(f) lorsque arrete(f, f) vaut True, puis lorsqu'elle vaut False.
On considère l'appel paradoxe(paradoxe).

a) Supposer que arrete(paradoxe, paradoxe) renvoie True et aboutir à une contradiction.

b) Supposer que arrete(paradoxe, paradoxe) renvoie False et aboutir à une contradiction.
En déduire que la fonction arrete ne peut pas exister. Énoncer le résultat de décidabilité ainsi établi.
Expliquer en quoi cette démonstration utilise le fait qu'un programme peut être donné en argument d'un autre programme.

Résoudre

À s'entraîner ! 9 exercices dans cette section

★☆☆ On considère la fonction suivante, qui prend en paramètre un entier naturel n. 1. Donner…★☆☆ On souhaite écrire une fonction maximum(tab) qui renvoie le plus grand élément d'une…★☆☆ On considère la fonction récursive suivante. 1. Donner la valeur renvoyée par…

L'essentiel

Une spécification précise ce qu'une fonction reçoit et renvoie. Un jeu de tests (cas courants, limites, pièges) et des assert permettent de repérer les bugs, mais ne prouvent pas la correction.
Une fonction récursive a un cas de base, un cas récursif qui se ramène à un problème plus petit, et une quantité qui décroît strictement : c'est ce qui assure la terminaison.
Plusieurs appels récursifs par exécution peuvent faire exploser le coût (Fibonacci, Hanoï en $2^n - 1$). Les propriétés sur le nombre d'appels se démontrent par récurrence ; la mémoïsation évite les recalculs.
Diviser pour régner : le tri fusion coûte de l'ordre de $n \log_2 n$, contre $n^2$ pour un tri naïf.
Programmation dynamique : on stocke les solutions des sous-problèmes. Pour le rendu de monnaie, $m(s) = 1 + \min m(s - p)$ ; l'algorithme glouton n'est pas toujours optimal.
Le problème de l'arrêt est indécidable : aucun programme ne peut décider, pour tout programme et toute donnée, si l'exécution se termine.