Récursivité#
Approfondissement
Une fonction récursive est une fonction qui s’appelle elle-même. Elle doit toujours posséder :
un cas de départ, qui donne directement un résultat ;
un appel récursif qui rapproche progressivement de ce cas de départ.
La factorielle vérifie :
Pour calculer fact(5), Python attend le résultat de fact(4), qui attend fact(3), et
ainsi de suite jusqu’à fact(0). Les appels descendent d’abord jusqu’au cas de départ ; les
résultats remontent seulement ensuite, un appel après l’autre.
fact(4)→
4 × fact(3)→
4 × 3 × fact(2)→
4 × 3 × 2 × fact(1)→
4 × 3 × 2 × 1 × fact(0)
fact(0) = 1
fact(0) = 1→
fact(1) = 1 × 1 = 1→
fact(2) = 2 × 1 = 2→
fact(3) = 3 × 2 = 6→
fact(4) = 4 × 6 = 24
La fonction peut être essayée avec d’autres entiers positifs. Un entier négatif n’atteindrait jamais le cas n == 0 : sa définition suppose donc \(n\geqslant0\).
À essayer. Écrire une fonction récursive qui calcule \(1+2+3+\cdots+n\) pour un entier \(n\geqslant1\).
Besoin d’un indice ?
Cherche le cas le plus simple, puis exprime la somme jusqu’à \(n\) à l’aide de la somme jusqu’à \(n-1\).
Permutations et sous-ensembles#
Ces deux problèmes utilisent la même idée que la factorielle : résoudre un problème plus petit, puis construire la réponse complète.
Pour obtenir les permutations de ["A", "B", "C"], on peut d’abord calculer celles de
["B", "C"], puis insérer "A" à chacune des trois positions possibles. Le cas de départ
est la liste vide, qui possède une seule permutation : [[]].
Construire toutes les permutations. Écrire une fonction permutations(L) qui renvoie
toutes les permutations de la liste L, sans utiliser itertools. Pour trois éléments
distincts, six listes doivent être obtenues.
Pour construire les sous-ensembles de taille k, chaque élément offre deux choix : le prendre,
et chercher encore k-1 éléments dans la suite de la liste ; ou ne pas le prendre, et chercher
encore k éléments. Les appels doivent finir lorsque k == 0 ou lorsqu’il ne reste plus
assez d’éléments.
Choisir plusieurs éléments. Écrire une fonction sous_ensembles(L, k) qui renvoie toutes
les sous-listes de k éléments distincts de L, sans compter plusieurs fois le même choix
et sans utiliser itertools.
La tour de Hanoï#
Trois tiges et des disques de tailles différentes sont utilisés. Un seul disque peut être déplacé à la fois et un grand disque ne peut jamais être posé sur un plus petit. L’objectif est de déplacer toute la pile de la tige A vers la tige C.
Pour déplacer une pile de n disques de A vers C :
déplacer les
n-1plus petits de A vers B, en utilisant C ;déplacer le grand disque de A vers C ;
déplacer les
n-1plus petits de B vers C, en utilisant A.
Les étapes 1 et 3 sont exactement le même problème, avec un disque de moins. Le cas de départ
est simple : avec un seul disque, un seul déplacement suffit. Pour trois disques, la méthode
produit 7 déplacements ; pour n disques, elle en produit \(2^n-1\).
Un déplacement est mémorisé par un couple comme ("A", "C") : le premier texte est la tige
de départ, le second la tige d’arrivée. La liste complète pour trois disques contient donc sept
couples, dans le même ordre que le schéma.
À programmer. Écrire une fonction récursive hanoi(n, depart, arrivee, intermediaire) qui
renvoie la liste des déplacements sous la forme de couples (origine, destination).
Conclusion#
Ces prolongements transforment une idée mathématique en une suite d’étapes assez précises pour être exécutées. Le programme ne remplace pas le raisonnement : il oblige à l’organiser, puis permet de tester rapidement ce qu’il produit.
Si tu es arrivé jusqu’ici, bravo : tu disposes maintenant d’outils solides pour explorer d’autres problèmes.
Choisir une autre partie