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

Écrire et analyser une fonction récursive

Une fonction est récursive lorsqu'elle s'appelle elle-même. Pour qu'elle soit correcte, elle comporte toujours deux parties :

Regardons une fonction qui calcule $n!$ :

def factorielle(n):

    if n == 0:          # cas de base

        return 1

    else:               # cas récursif

        return n * factorielle(n - 1)

Chaque appel attend le résultat de l'appel suivant : les appels s'empilent dans la pile d'appels, puis les résultats remontent.

Terminaison

Une fonction récursive ne s'arrête que si, à chaque appel, une quantité entière décroît strictement et reste positive (ou plus généralement ne peut pas décroître indéfiniment). Pour factorielle, c'est $n$ : on passe de $n$ à $n-1$, et on s'arrête en $0$. Justifier la terminaison, c'est nommer cette quantité (le variant) et dire pourquoi elle atteint le cas de base.

Les opérations sur les chaînes et les listes se prêtent bien à la récursivité : on traite un élément (ou deux extrémités), puis on rappelle la fonction sur le reste, obtenu par une tranche (s[1:], s[1:-1]). La longueur du reste est alors le variant.

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 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

Mise au point : spécification, assertions et jeux de tests

Une fonction doit avoir une spécification : ce qu'elle prend en paramètre (préconditions), ce qu'elle renvoie (postcondition). On l'écrit dans la docstring.

def maximum(tab):

    """tab : liste non vide d'entiers.

    Renvoie le plus grand élément de tab."""

    m = tab[0]

    for x in tab:

        if x > m:

            m = x

    return m

Les bugs classiques

Quelques causes d'erreurs à connaître : une initialisation inadaptée (ici, m = 0 serait faux pour une liste de nombres négatifs), un indice qui sort du tableau (IndexError), une conditionnelle non exhaustive (un cas oublié), la comparaison de flottants avec == (0.1 + 0.2 == 0.3 est False), un mauvais nommage de variable.

Les assertions

Une assertion vérifie une précondition et arrête le programme avec un message clair si elle est fausse :

def puissance(x, n):

    assert n >= 0, "n doit être un entier naturel"

    ...

Si n est négatif, Python lève une AssertionError tout de suite, au lieu de partir dans une récursion sans fin.

Le jeu de tests

Un jeu de tests est un ensemble de cas dont on connaît le résultat. Un bon jeu contient des cas ordinaires et des cas limites : liste à un seul élément, valeurs négatives, valeur répétée, résultat en première ou en dernière position.

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

assert maximum([-5, -2, -9]) == -2   # cas limite : que des négatifs

assert maximum([7]) == 7             # un seul élément

Réussir des tests ne prouve pas qu'une fonction est correcte, mais en échouer prouve qu'elle est fausse.

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

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

Coût d'une récursion : Fibonacci et tours de Hanoï

Quand une fonction fait deux appels récursifs, le nombre d'appels peut exploser. Étudions la suite de Fibonacci.

def fib(n):

    if n <= 1:

        return n

    else:

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

Notons $C(n)$ le nombre d'appels. On raisonne ainsi : un appel fib(n) avec $n \geqslant 2$ compte pour 1, puis déclenche tous les appels de fib(n-1) et de fib(n-2). Donc $C(n) = 1 + C(n-1) + C(n-2)$, avec des cas de base à compter à part. Sur l'arbre ci-dessus, fib(4) fait 9 appels.

Démontrer une formule sur un nombre d'appels

Pour prouver une formule du type « pour tout $n$, $C(n) = \dots$ », on utilise la récurrence (à deux pas ici, car $C(n)$ dépend de deux termes précédents) :

Initialisation : on vérifie la formule aux premiers rangs ($n = 0$ et $n = 1$).
Hérédité : on suppose la formule vraie aux rangs $n-1$ et $n-2$, et on la démontre au rang $n$ en utilisant la relation de récurrence.
On conclut.

Tours de Hanoï : le même raisonnement

Pour hanoi(n, ...), on compte les déplacements $h(n)$ : un appel déplace $n-1$ disques, puis 1 disque (l'affichage), puis encore $n-1$ disques. On obtient donc une relation de la forme $h(n) = 2\,h(n-1) + 1$ avec $h(0) = 0$. En calculant les premières valeurs, on devine la formule, puis on la prouve par récurrence.

Éviter les répétitions : la mémoïsation

On peut ne calculer chaque fib(k) qu'une fois en conservant les résultats dans un dictionnaire :

def fib_memo(n, 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

Le nombre d'appels devient proportionnel à $n$ au lieu de croître de façon exponentielle.

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 et programmation dynamique

Diviser pour régner : le tri fusion

Le principe : diviser le problème en sous-problèmes plus petits, résoudre chacun (souvent récursivement), puis combiner les résultats.

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

La fusion de deux listes triées l1 et l2 compare les deux plus petits éléments restants et prend le plus petit :

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:]

Par exemple, fusion([1, 2], [0, 3]) renvoie [0, 1, 2, 3]. Le tri fusion coûte de l'ordre de $n \log_2 n$ opérations, contre $n^2$ pour les tris simples : le $\log_2 n$ compte le nombre de fois qu'on peut couper en deux une liste de taille $n$.

Programmation dynamique : le rendu de monnaie

Un algorithme glouton fait à chaque étape le choix qui semble le meilleur sur le moment. Il n'est pas toujours optimal.

Rendre 8 centimes avec les pièces 1, 4 et 5

Algorithme glouton, puis programmation dynamique.

Glouton : on prend la plus grande pièce possible. $8 = 5 + 1 + 1 + 1$ : 4 pièces.

Mieux : $8 = 4 + 4$ : 2 pièces seulement. Le glouton n'est donc pas optimal ici.

Programmation dynamique : on note $m(s)$ le nombre minimal de pièces pour la somme $s$. On a $m(0) = 0$ et, pour $s \geqslant 1$, $m(s) = 1 + \min m(s - p)$ où $p$ décrit les pièces telles que $p \leqslant s$. On remplit un tableau en partant des petites sommes :

$s$	0	1	2	3	4	5	6	7	8
$m(s)$	0	1	2	3	1	1	2	3	2

Par exemple $m(8) = 1 + \min(m(7), m(4), m(3)) = 1 + \min(3, 1, 3) = 2$.

Calcule $m(7)$ avec la formule, dans ton cahier.

$m(7) = 1 + \min(m(6), m(3), m(2)) = 1 + \min(2, 3, 2) = 3$.

La programmation dynamique résout d'abord les petits sous-problèmes, mémorise leurs solutions dans un tableau, et s'en sert pour les plus grands : on ne recalcule jamais deux fois la même chose, comme avec fib_memo.

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

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 aussi une donnée : le problème de l'arrêt

En Python, une fonction peut être passée en paramètre d'une autre fonction : f(f) est possible. Un programme est donc une donnée comme une autre (texte, fichier). C'est ce qui permet à un compilateur ou à un antivirus d'analyser des programmes.

Peut-on alors écrire un programme arrete(f, x) qui dit, pour tout programme f et toute donnée x, si f(x) se termine ou tourne indéfiniment ? Ce serait très utile pour détecter les boucles infinies. Le résultat est négatif : le problème de l'arrêt est indécidable.

Pourquoi ? Un raisonnement par l'absurde

On suppose que arrete existe et se termine toujours. On construit :

def paradoxe(f):

    if arrete(f, f):

        while True:

            pass

    else:

        return 0

paradoxe fait le contraire de ce que prédit arrete : si arrete annonce que f(f) se termine, paradoxe boucle indéfiniment ; sinon, elle se termine. Puis on regarde ce qui se passe pour paradoxe(paradoxe) :

si arrete(paradoxe, paradoxe) renvoie True, alors paradoxe(paradoxe) entre dans la boucle infinie : il ne se termine pas, contradiction avec la réponse True ;
si elle renvoie False, alors paradoxe(paradoxe) renvoie 0 : il se termine, contradiction avec False.

Dans les deux cas, on aboutit à une contradiction. L'hypothèse de départ est 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

Pour revenir au début : on est sûr qu'une récursion atteint « la dernière poupée » grâce à un variant qui décroît jusqu'au cas de base, et on mesure son coût en comptant les appels.

À 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 fonction récursive a un cas de base et un cas récursif qui se rapproche du cas de base ; la terminaison se justifie par un variant entier strictement décroissant.
Une spécification, des assertions et un jeu de tests (avec cas limites) permettent de repérer les bugs ; un test réussi ne prouve pas la correction.
Le nombre d'appels d'une fonction à deux appels récursifs (comme fib) croît très vite ; on le démontre par récurrence et on l'évite par la mémoïsation.
Diviser pour régner (tri fusion, en $n \log_2 n$) : diviser, résoudre, combiner. Programmation dynamique : mémoriser les solutions de sous-problèmes qui se chevauchent (rendu de monnaie) ; le glouton n'est pas toujours optimal.
Un programme est une donnée ; le problème de l'arrêt est indécidable (démonstration par l'absurde avec paradoxe).