Chap 5 – La récursivité

Chapitre 5 – La récursivité Une autre manière de répéter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Une première fonction récursive (récursion “descendante” uniquement) . . . . . . . . . . . . . . . . . . 3

Accueil

Chapitre 5 – La récursivité Chapitre 5 – La récursivité Une autre manière de répéter Jusqu’à présent, nous avons appris à répéter des instructions grâce aux différentes boucles du C++, comme for, while ou do…while. Ces structures permettent d’exécuter plusieurs fois les mêmes instructions en faisant évoluer progressivement une ou plusieurs variables. Il existe cependant une autre manière de résoudre certains problèmes. Au lieu d’utiliser une boucle, une fonction peut tout simplement s’appeler elle-même. Cette technique porte le nom de récursivité. La récursivité est une approche très élégante qui permet de résoudre naturellement certains problèmes dont la structure se répète. On la rencontre dans de nombreux domaines de l’informatique : parcours d’arbres, exploration de labyrinthes, recherche dans des dossiers, algorithmes de tri, intelligence artificielle et bien d’autres encore. Avant d’étudier cette nouvelle technique, il est important de bien comprendre qu’il existe deux grandes façons de répéter une opération. Utilise une boucle (for, while, La répétition est contrôlée par une variable de boucle. Très adaptée aux traitements répétitifs Une fonction s’appelle elle-même. La répétition est obtenue par des appels successifs de la fonction. Très adaptée aux problèmes qui se décomposent naturellement en sousproblèmes plus petits. Aucune de ces deux approches n’est systématiquement meilleure que l’autre. Certaines situations se prêtent naturellement à une solution itérative, tandis que d’autres sont beaucoup plus simples à exprimer de manière récursive. Un bon programmeur doit connaître les deux techniques afin de choisir la plus adaptée au problème qu’il souhaite • Une itération répète des instructions grâce à une boucle. • Une récursivité répète un traitement en faisant s’appeler une fonction elle-même. • Les deux approches permettent souvent de résoudre un même problème. Comprendre la récursivité Avant d’écrire notre première fonction récursive, essayons de comprendre le principe de la récursivité à l’aide de quelques situations de la vie courante. Chaque appel récursif rapproche progressivement le programme du cas de base, c’est-à-dire du moment où la fonction peut terminer son travail sans effectuer de nouvel appel. Autrement dit, au lieu de résoudre directement un problème parfois complexe, on le simplifie petit à petit jusqu’à obtenir un cas très simple, dont la solution est immédiate. Imaginez une poupée gigogne (ou poupée russe). Lorsque vous l’ouvrez, vous découvrez une seconde poupée. À l’intérieur de celle-ci se trouve une troisième poupée. Puis une quatrième. Et ainsi de suite, jusqu’à la dernière, qui ne contient plus rien. Chaque poupée est construite sur le même principe que la précédente, mais elle est simplement plus proche du but qui est : ne rien contenir.

Accueil

Chapitre 5 – La récursivité La récursivité fonctionne exactement de la même manière : chaque appel de fonction traite une version du même problème, qui à chaque itération s’approche d’une solution élémentaire. La récursivité consiste toujours à rapprocher progressivement un problème d’un cas très simple dont la solution est immédiate. Ce cas particulier, appelé cas de base ou condition d’arrêt, est indispensable. Sans lui, les appels récursifs continueraient indéfiniment. Une première fonction récursive (récursion “descendante” uniquement) Imaginons que vous deviez annoncer un compte à rebours avant le décollage d’une fusée. Vous commencez par Le travail n’est pas terminé. Il reste exactement le même travail à effectuer, mais en partant de 4. Après avoir annoncé 4, il reste exactement le même travail, mais en partant de 3. Enfin, lorsque le compte atteint 0, il n’y a plus rien à annoncer : le compte à rebours est terminé. Chaque étape rapproche donc naturellement du cas où le travail est terminé. • Une bonne fonction récursive ne cherche jamais à résoudre tout le problème. Elle résout seulement une petite partie, puis laisse la même fonction résoudre le reste. Fonction « Compte à rebours » void compteARebours(int n) std::cout << n << ’\n’; // Travail avant compteARebours(n − 1); // Appel recursif

Accueil

Chapitre 5 – La récursivité Voilà une variation de la fonction « compte à rebours ». Pouvez-vous prédire le résultat ? void compteARebours(int n) std::cout << n << ’\n’; compteARebours(n − 1); std::cout << « Je remonte » << std::endl; Prenez le temps de réfléchir avant de lire la suite du chapitre. Jusqu’à présent, nous avons observé qu’une fonction récursive commence par descendre jusqu’au cas de base, puis remonte progressivement. Mais une question se pose naturellement : Comment le programme sait-il où reprendre son exécution après chaque appel récursif ? Pour répondre à cette question, imaginons un escalier numéroté de 10 à 1. Nous nous trouvons au sommet, sur la marche 10. Notre objectif est de calculer la somme des numéros de toutes les marches. Au lieu d’additionner immédiatement les valeurs, nous décidons de descendre jusqu’à la première marche. Ce n’est qu’une fois arrivé en bas que nous commencerons à remonter en effectuant les additions. Le programme suivant réalise exactement cette opération. int sommeNEntiers(int n) std::cout << « Je descends sur la marche  » int sommePartielle = sommeNEntiers(n − 1); int resultat = sommePartielle + n; std::cout << « Je remonte a la marche  »

Accueil

Chapitre 5 – La récursivité std::cout << « \nSomme =  » << sommeNEntiers(10) Avant de comprendre le calcul lui-même, observons ce qui se passe pendant la descente. À chaque appel de la fonction, le programme doit mémoriser l’endroit où il devra reprendre son exécution une fois l’appel récursif terminé. Pour cela, il place les informations nécessaires au sommet d’une structure appelée pile d’appels (en anglais call stack). Au début de l’exécution, la pile contient uniquement la fonction main(). Après l’appel de sommeNEntiers(10) : —————–sommeNEntiers(10) —————–sommeNEntiers(9) —————–sommeNEntiers(10) —————–sommeNEntiers(8) —————–sommeNEntiers(9) —————–sommeNEntiers(10) La pile continue ainsi à grandir jusqu’à atteindre la marche 1. À cet instant, la fonction sommeNEntiers(1) atteint le cas de base et renvoie simplement la valeur 1. La pile commence alors à se vider. La fonction sommeNEntiers(2) reprend son exécution exactement après l’appel récursif. Elle reçoit la valeur 1, calcule : et renvoie la valeur 3. La fonction sommeNEntiers(3) reprend ensuite son exécution. Elle reçoit la valeur 3, calcule :

Accueil

Chapitre 5 – La récursivité et renvoie la valeur 6. et ainsi de suite jusqu’à la marche 10. Finalement, la dernière fonction renvoie : Cette valeur est ensuite reçue par la fonction main(), qui l’affiche à l’écran. La sortie exact est : Somme = Je descends sur la marche 10 Je descends sur la marche 9 Je descends sur la marche 8 Je descends sur la marche 7 Je descends sur la marche 6 Je descends sur la marche 5 Je descends sur la marche 4 Je descends sur la marche 3 Je descends sur la marche 2 Je descends sur la marche 1 Je remonte a la marche 2 : 1 + 2 = 3 Je remonte a la marche 3 : 3 + 3 = 6 Je remonte a la marche 4 : 6 + 4 = 10 Je remonte a la marche 5 : 10 + 5 = 15 Je remonte a la marche 6 : 15 + 6 = 21 Je remonte a la marche 7 : 21 + 7 = 28 Je remonte a la marche 8 : 28 + 8 = 36 Je remonte a la marche 9 : 36 + 9 = 45 Je remonte a la marche 10 : 45 + 10 = 55 Program ended with exit code: 0 • Une fonction récursive ne perd jamais sa place dans le programme. • Lorsqu’elle appelle une nouvelle fois la même fonction, son exécution est simplement mise en attente. • Toutes les informations nécessaires pour reprendre l’exécution sont conservées dans la pile d’appels. • Les fonctions reprennent ensuite leur exécution dans l’ordre inverse de leur appel. La factorielle est souvent utilisée pour illustrer la récursivité. Vous êtes maintenant capable de l’écrire vousmême en quelques lignes. Maintenant que nous avons compris le rôle de la pile d’appels et le déroulement de la récursivité, nous pouvons simplifier la fonction. Les variables intermédiaires, qui étaient utiles pour suivre le raisonnement, ne sont plus nécessaires.

Accueil

Chapitre 5 – La récursivité int sommeNEntiers(int n) return n + sommeNEntiers(n − 1); std::cout << sommeNEntiers(10) << ’\n’; On pourrait tout aussi bien écrire if (n == 1) return 1; Cependant pour des raisons pédagogiques (chaque instruction mérite sa ligne) on utilisera la seconde écriture ! Les Tours de Hanoï constituent l’un des exemples les plus célèbres de récursivité. Le jeu est composé de trois tours, notées A, B et C, ainsi que d’une pile de disques de diamètres différents. Au départ, tous les disques sont empilés sur une même tour, du plus grand au plus petit. Le but est de déplacer toute la pile sur une autre tour en respectant les deux règles suivantes : • un seul disque peut être déplacé à la fois ; • un disque plus grand ne peut jamais être posé sur un disque plus petit. Avant d’écrire le moindre programme, essayons de résoudre le problème nous-mêmes. Commencez par dessiner trois tours et trois disques numérotés de 1 à 3, le disque 1 étant le plus petit. Chaque déplacement sera noté sous la forme • déplacer le disque 1 ; • de la tour A vers la tour B. Essayez maintenant de résoudre le problème avant de poursuivre la lecture.

Accueil

Chapitre 5 – La récursivité – un seul disque est déplacé ; – aucun disque plus grand n’est jamais posé sur un disque plus petit. La pile finale est bien sur B : 3 − 2 − 1. Recommencez le même exercice avec quatre disques. Cette fois, ne cherchez pas à résoudre complètement le problème. Arrêtez-vous dès que les trois plus petits disques sont empilés sur une autre tour. Que remarquez-vous ? Les trois plus petits disques se retrouvent exactement dans la même configuration que le problème précédent. Autrement dit, le problème à quatre disques contient le problème à trois disques. • Le problème des Tours de Hanoï possède une propriété remarquable : Pour déplacer une pile de n disques, il faut d’abord savoir déplacer une pile de n − 1 disques. • Nous venons de découvrir le principe fondamental de la récursivité. Nous nous arrêtons ici. Inutile de poursuivre les déplacements. Observez simplement la configuration obtenue. Les trois plus petits disques sont maintenant empilés exactement comme au début de l’exercice précédent. Nous avons donc retrouvé le problème à trois disques. Les essais réalisés avec trois puis quatre disques nous ont permis de faire une observation importante : le problème semble toujours se reproduire avec un disque de moins. Supposons maintenant que nous disposions d’une pile de n disques. Comment déplacer cette pile complète sur une Le plus grand disque est situé tout en bas de la pile. Tant qu’il est recouvert par les n − 1 autres disques, il est impossible de le déplacer. Il faut donc commencer par déplacer les n − 1 plus petits disques sur la troisième tour.

Accueil

Chapitre 5 – La récursivité Nous pouvons alors déplacer le plus grand disque vers sa tour de destination. Il ne reste plus qu’à replacer les n − 1 petits disques au-dessus de lui. Nous obtenons ainsi une méthode générale. • Pour déplacer une pile de n disques : • déplacer les n − 1 plus petits disques vers la tour auxiliaire ; • déplacer le plus grand disque vers la tour de destination ; • déplacer les n − 1 plus petits disques sur le plus grand disque. Remarquez que les première et troisième étapes consistent exactement à résoudre le même problème, mais avec une pile contenant un disque de moins. Nous retrouvons donc naturellement le principe de la récursivité. Exemple avec avec 5 disques Fig. 2 – Schéma pour n = 5. Les rôles des tours A, B et C sont interchangeables. Dans notre raisonnement, A est toujours la tour de départ, C la tour d’arrivee et B la tour auxiliaire. Mais rien n’empêche de choisir une autre tour comme Écriture du programme Nous savons maintenant comment résoudre le problème des Tours de Hanoï. Il ne reste plus qu’à traduire notre raisonnement en langage C++. Pour déplacer une pile de disques, notre fonction devra connaître quatre informations : • le nombre de disques à déplacer ; • la tour de départ ; • la tour de destination ; • la tour auxiliaire. Nous pouvons donc commencer par écrire la déclaration de la fonction.

Accueil

Chapitre 5 – La récursivité Le paramètre n représente le nombre de disques à déplacer. Les trois paramètres de type char contiennent simplement le nom des trois tours. Ils pourront prendre les valeurs ’A’, ’B’ et ’C’. Avant d’écrire le reste de la fonction, une question importante se pose. Quand la récursivité doit-elle s’arrêter ? Comme toute fonction récursive, notre fonction doit posséder un cas de base. Celui-ci est particulièrement simple. S’il ne reste qu’un seul disque à déplacer, aucune réflexion n’est nécessaire : il suffit de le déplacer directement vers sa tour de destination. Le début de notre fonction devient alors : L’instruction return met immédiatement fin à la fonction. Si nous arrivons dans ce cas, il est inutile de poursuivre l’exécution. Nous pouvons maintenant nous occuper du cas général. Reprenons le raisonnement découvert dans le paragraphe précédent. Pour déplacer une pile de n disques, il faut : 1. déplacer les n − 1 plus petits disques vers la tour auxiliaire ; 2. déplacer le plus grand disque vers la tour de destination ; 3. déplacer les n − 1 plus petits disques sur le plus grand disque. Il suffit maintenant de traduire chacune de ces trois étapes en C++. La première étape consiste à déplacer les n − 1 plus petits disques. Cette instruction ressemble beaucoup à la déclaration de la fonction. La seule différence est que le nombre de disques a diminué d’une unité et que les rôles des tours ont changé. Nous pouvons ensuite déplacer le plus grand disque. Enfin, il reste à déplacer les n − 1 plus petits disques sur le plus grand.

Accueil

Chapitre 5 – La récursivité En réunissant toutes ces parties, nous obtenons la fonction complète. Cette fonction ne fait finalement rien d’autre que reproduire fidèlement le raisonnement que nous avons construit Elle ne contient aucun « tour de magie ». Chaque appel récursif correspond simplement à l’une des étapes de notre méthode de résolution. Le programme complet s’écrit donc ainsi : Programme 1 – Programme Les tours de Hanoï std::cout << depart <<  » −>  » << arrivee << ’\n’;

Accueil

Chapitre 5 – La récursivité // Deplacer les n−1 plus petits disques hanoi(n − 1, depart, auxiliaire, arrivee); // Deplacer le plus grand disque std::cout << depart <<  » −>  » << arrivee << ’\n’; // Deplacer les n−1 plus petits disques hanoi(n − 1, auxiliaire, arrivee, depart); int main(int argc, const char ∗ argv[]) hanoi(20, ’A’, ’C’, ’B’); Avec 20 disques le nombre de déplacements est de 2n − 1 = 1048575.

Accueil

Chapitre 5 – La récursivité Σ Complément mathématique Le nombre de déplacements effectués par notre fonction récursive vérifie la relation suivante : T (n) = 2T (n − 1) + 1, où T (n) désigne le nombre de déplacements nécessaires pour une pile de n disques. Cette relation traduit exactement notre algorithme : 1. déplacer les n − 1 plus petits disques ; 2. déplacer le plus grand disque (un seul déplacement) ; 3. déplacer à nouveau les n − 1 plus petits disques. Calculons les premières valeurs : T (2) = 2 × 1 + 1 = 3, T (3) = 2 × 3 + 1 = 7, T (4) = 2 × 7 + 1 = 15, T (5) = 2 × 15 + 1 = 31. On reconnaît immédiatement la suite 1, 3, 7, 15, 31, . . . qui s’écrit plus simplement Les lecteurs connaissant le triangle de Pascal remarqueront peut-être que la somme des nombres d’une ligne vaut toujours une puissance de deux : Les Tours de Hanoï conduisent eux aussi aux puissances de deux, car chaque problème se décompose en deux sous-problèmes identiques. Le terme −1 provient simplement du fait qu’il faut ajouter un unique déplacement entre les deux appels récursifs. On peut d’ailleurs écrire : T (n) + 1 = 2 T (n − 1) + 1 , ce qui conduit immédiatement à La légende raconte que, dans un temple de Bénarès, des moines déplacent sans interruption une tour de 64 disques selon les règles des Tours de Hanoï. Lorsque le dernier déplacement sera effectué… le monde prendra fin. 264 − 1 = 18 446 744 073 709 551 615

Accueil

Chapitre 5 – La récursivité Soit environ 18, 4 milliards de milliards de déplacements ! Même en déplaçant un disque par seconde, il faudrait environ 585 milliards d’années. Pour donner un ordre de grandeur, l’âge actuel de l’Univers est estimé à environ 13, 8 milliards d’années. La récursivité permet à une fonction de résoudre un problème en le ramenant à un problème plus petit de même nature. Toute fonction récursive doit posséder un cas de base, sans lequel les appels se poursuivraient indéfiniment. Les exemples étudiés dans ce chapitre ont également montré que la récursivité peut produire un code très élégant, mais qu’elle utilise la pile d’appels et peut parfois conduire à un très grand nombre d’opérations. Une fonction récursive : — s’appelle elle-même ; — doit toujours posséder un cas de base ; — résout généralement un problème en le ramenant à un problème plus petit ; — utilise la pile d’appels pour conserver les appels encore inachevés.

Accueil

cpp-Chap5- Chapitre 5 – La récursivité

Accueil