Magie de la récursivité

Il y a récursivité quand quelque chose fait référence à ce quelque chose en question et ceci pour tout et n’importe quoi. Je semble aborder légèrement ce phénomène mais il existe dans tous les domaines et tout autour de nous. A priori le fait de faire appel à soi-même pour se définir semble être et peut-être considéré à juste titre comme étant une douce folie conduisant à toutes sortes de cercles vicieux et de paradoxes, ce qui arrive sans aucun doute si l’on n’y prend garde. Cependant la récursivité qui est un des concepts auto-référents se place dans un cadre bien plus précis que ce que je viens de dire.

La récursivité dans les images est facile à voir et à concevoir. Une image bien connue est celle du couvercle de la vache qui rit qui contient une vache avec deux boites de vache qui rit en guise de boucles d’oreilles. Donc dans chacune des boucles d’oreille, on peut encore distinguer une vache qui porte deux boites de vache qui rit en guise de boucles d’oreilles. En conséquence, on peut imaginer voir dans l’image une infinité possibles de dessins similaires mais à chaque niveau, l’image des boites devenant de plus en plus petite plus rien ne peut apparaître. La récursivité est un cas particulier d’auto-référence qui n’est pas un cercle vicieux grâce à l’existence d’un ordre. Dans le cas de la vache qui rit, l’auto-référence se fait bien dans le cadre d’un dessin plus petit et comme cet ordre est bien fondé, le processus récursif se termine. Dans le dessin de la vache qui rit, la bonne fondation ( la base, l’origine si vous voulez ) est l’ image la plus petite que l’on puisse distinguer. Remarquer que l’imagination peut renier cette bonne fondation, se débarrasser de ce monde fini et imaginer à l’infini des images infiniment plus petites. Si vous voulez compter le nombre de vaches qui rit que cela implique, c’est facile :au premier niveau, vous en voyez 2, au deuxième niveau 4, au troisième 8, … au dixième 1024, … au nième 2n.

Allez lançons nous dans un exemple ludique de récursivité : les fameuses tours de Hanoï. Pour jouer vous devez posséder une tour qui est semblable à un jeu d’anneaux à empiler que l’on donne à un enfant de deux ans pour lui apprendre à empiler des anneaux sur le mat du plus grand au plus petit. Vous devez en plus avoir deux mats vides d’anneaux. L’anneau qui contient les anneaux est l’anneau de départ. Un des mats est celui d’arrivée où l’on doit aller placer les anneaux ordonnés du plus grand au plus petit. L’autre mat vide servant d’intermédiaire. Le jeu consiste à déplacer les anneaux depuis le mat de départ vers le mat d’arrivée avec un nombre de déplacements minimum tout en respectant les règles suivantes :

  • Ne déplacer qu’un anneau à la fois.
  • Ne placer un anneau que sur un autre anneau plus grand que lui quand le mat contient déjà des anneaux.

Regarder jouer cette petite fille ici !
Je vous souhaite bien du plaisir si vous voulez jouer avec une tour à dix anneaux en utilisant ce site.

Le mathématicien E. Lucas qui est l’auteur de ce jeu mathématique l’a accompagné de la légende suivante :
Dans le grand temple indien, il y aurait selon la légende trois grandes aiguilles de diamant, plantées dans une cour ou au sommet de trois pics himalayens si vous préférez. Sur une de ces aiguilles, Dieu a placé 64 disques d’or les uns sur les autres, du plus grand au plus petit plus petit car ils sont de diamètres de plus en plus petits. Incessamment, les moines sont tenus par Dieu de transporter la tour de l’ aiguille origine sur la troisième en respectant les règles que nous venons d’indiquer. La prophétie annonce que quand tout sera fini le temple s’écroulera et ce sera l’annonce de la fin des temps.

Revenons à notre problème. Nous allons exprimer de façon récursive et très simplement la stratégie à suivre pour déplacer correctement les anneaux. En effet si le mat de départ ne contient qu’un anneau, il suffit n’est-ce pas de le transporter directement en un seul mouvement sur le mat d’arrivée. C’est la base de la récursion. Pour la solution de ce jeu, l’ordre bien fondé qui sert à trouver la récursion est celui du nombre des anneaux du jeu. Maintenant pour trouver la solution récursive certains regardent comment faire avec 2, puis trois anneaux et effectuent une généralisation de ce qu’ils trouvent comme stratégie de jeu au cas d’ un nombre quelconque d’anneaux. Faites le si vous le voulez, cela vous aidera sans doute à comprendre ce qui suit mais moi je veux vous donner une idée du pouvoir magique de la récursivité alors je vais vous l’expliquer autrement. Pour trouver une solution récursive pour un nombre n d’anneaux quelconques quand on connait l’ordre sous-jacent que l’on veut utiliser cela devient vraiment miraculeux. Il suffit de considérer que l’on sait faire pour tout les cas inférieurs à n ! ( Cela s’apparente au raisonnement par récurrence ). Ceci étant dit, on peut voir simplement que si l’on sait jouer avec n -1 anneaux pour les placer sur le mat intermédiaire, en utilisant le mat d’arrivée comme intermédiaire bien entendu, il suffit alors de déplacer l’anneau restant sur le mat d’arrivée et ensuite de jouer à placer les n-1 anneaux du mat intermédiaire sur le mat d’arrivée en utilisant cette fois le mat de départ comme intermédiaire. Et voilà que nous avons une solution auto-référente vide de tout cercle vicieux grâce au bon ordre des entiers. Cette solution récursive nous donne une stratégie générale pour le jeu à un nombre quelconque d’anneaux au départ. On peut aussi comprendre que pour déplacer l’anneau le plus grand, il faut déjà avoir su déplacer les n – 1 anneaux du dessus sur le mat intermédiaire et donc qu’il faudra bien ensuite déplacer ces n-1 anneaux du mat intermédiaire vers le mat d’arrivée. Cette vision des choses nous permet d’affirmer que la stratégie dont nous allons hériter est optimale : elle nous donne le nombre de déplacements minimum.

Pour mieux voir la magie se déployer, nous allons être obligés d’abstraire un peu ce que nous venons de dire en introduisant des lettres symboliques. Dans ce qui suit la lettre J signifie jeu et la spécification du jeu doit se compléter en indiquant le nombre n d’anneaux en jeu, le mat de départ D, le mat d’arrivée A et le mat intermédiaire I dont on dispose au début du jeu. Nommer les mats avec des couleurs différentes si vous aimez mieux : bleu blanc rouge pourquoi pas et amusez vous à réécrire ce que nous allons maintenant développer. Donc le jeu à expliciter sera pour nous Jeu n D A I. Attention à l’ordre des lettres repérant les mats : le premier désignera toujours le mat de départ, le second celui de l’arrivée et le dernier l’intermédiaire donc quand on écrit Jeu 4 I D A par exemple ce la signifie que nous exprimons un jeu avec 4 anneaux sur le mat I au départ qui doit être placé sur le mat D à l’arrivée et en utilisant le mat A en intermédiaire. Quand au déplacement, appelons le Placer et nous écrirons donc Placer A D pour exprimer que nous déplacerons l’anneau du sommet du mat A vers le mat D. Maintenant je peux exprimer plus abstraitement que ci-dessus la stratégie :

  • Jeu 1 D A I = Placer D A
  • Jeu n D A I = Jeu n-1 D I A puis Placer D A puis Jeu n-1 I A D

Ainsi pour le jeu à 3 anneaux, nous pouvons développer la stratégie comme suit :
Jeu 3 D A I = Jeu 2 D I A puis Placer D A puis Jeu 2 I A D
= (Jeu 1 D A I puis Placer D I puis Jeu 1 A I D)
puis placer D A puis
(Jeu 1 I D A puis Placer I A puis Jeu 1 D A I)
= placer D A puis placer D I puis placer A I puis placer D A puis placer I D puis placer I A puis placer D A.

En fait on a un véritable programme pour ce jeu et Il vaut mieux laisser un ordinateur exécuter le programme récursif jeu 4 D A I pour 4 anneaux car suivre le développement de la stratégie manuellement est fastidieux. Il faut effectuer 15 déplacements pour 4 anneaux et déjà 1023 pour les 10 anneaux d’un jeu d’enfant. Pour n anneaux, on compte 2n – 1 déplacements ce qu’il est facile de compter en regardant la stratégie exprimée récursivement mais ce n’est pas le but de ce billet de d’expliquer ce calcul. Ainsi, avec 64 anneaux cela donne 264 – 1 déplacements soit 18 446 744 073 709 551 615 déplacements !

Toutes les démonstrations : du fait que la stratégie est optimale et du fait que le nombre de déplacements est 2n – 1, etc. peuvent se faire aisément par récurrence à partir de l’expression récursive du jeu.

La bonne fondation de l’ordre des entiers qui fait que la récursivité n’est pas un cercle vicieux est essentielle. Imaginez qu’il n’y ait pas de base, l’auto-référence serait infiniment descendante et vous absorberait dans un trou noir !

L’expression récursive permet d’ailleurs d’obtenir sans peine l’animation graphique du jeu. On pourrait aussi attacher des notes de musiques, par exemple aux anneaux ou au placement d’un anneau sur un mat et à bien d’autres choses encore, et par là obtenir un air de musique. On pourrait aussi, pourquoi pas, attacher des pinceaux symboliquement et obtenir une peinture. Certains confondent ces jeux intellectuels et ces résultats automatisés qui ont une certaine fascination magique avec la créativité mais je regrette : la créativité c’est autre chose ! Si j’osais je dirais que c’est tout a fait d’un autre ordre !

Publicités

À propos de chiendentbel

âgée mais éternellement jeune !

Publié le 27/11/2013, dans divertissement. Bookmarquez ce permalien. Commentaires fermés sur Magie de la récursivité.

Les commentaires sont fermés.

%d blogueurs aiment cette page :