Les Tours de Hanoï : un problème classique de récursion

On donne une casserole, un robinet d’eau et une gazinière à un polytechnicien en lui demandant de porter l’eau à ébullition. Le problème est simple à résoudre : il remplit la casserole d’eau, il la pose sur la gazinière, il allume le gaz, il attend et ça finit par bouillir. On donne maintenant à ce même polytechnicien les mêmes ingrédients, sauf que la casserole est déjà remplie d’eau. La solution qu’il emprunte est alors de vider la casserole. Cela prête à rire ? Il a choisi de se ramener au problème précédent, qu’il savait résoudre.

En mathématiques et en informatique, il est courant de résoudre un problème en le ramenant à un autre, déjà connu. La récursion fait partie des méthodes basées sur ce principe général.

Comment définir la récursion ?

Tout d’abord, connaissez-vous la récurrence ? Une fois que vous y êtes exposé, celle-ci paraît évidente. Imaginons que l’on cherche à prouver une propriété qui s’applique aux nombres entiers naturels. La récurrence dit que « Si c’est vrai pour 0 et si je sais transformer la preuve pour un entier naturel n en une preuve pour son successeur n 1 alors c’est vrai pour tout entier naturel. » En effet, la véracité pour 0 entraîne que je sais prouver que c’est aussi vrai pour son successeur 1, puis pour 2… bref, pour tout entier naturel que je peux atteindre en comptant.

La récursion s’apparente à la récurrence mais en prend en quelque sorte le contrepied, car elle s’intéresse à la résolution d’un problème complexe. Comme le dit Descartes, il faut « diviser chacune des difficultés afin de mieux les examiner et les résoudre ». Il s’agit de diviser le problème initial en sous-problèmes plus faciles à résoudre. C’est dans ce processus que la récursion intervient, lorsque la nature des sous-problèmes est la même que celle du problème initial. En outre, chaque sous-problème porte sur des données de plus petite taille que le précédent. Ainsi, un problème P(n) pourrait par exemple être résolu si l’on savait résoudre P(n-1) ou P(n/2). Or, dans le domaine des entiers naturels, on ne saurait faire décroître n sans finir par tomber sur un petit entier naturel comme par exemple 0 ou 1. Si l’on sait alors résoudre cet ultime problème P(0) ou P(1), alors le problème P(n) tout entier est finalement résolu.

Vous avez saisi le principe ? Testez un exemple classique que la récursion permet de résoudre : les tours de Hanoï. On doit déplacer une pyramide de disques d’une pique à une autre (il y en a trois en tout) avec une contrainte : on ne peut placer au-dessus d’un disque que des disques plus petits. Si l’on prend en main le disque au sommet de la pyramide, le plus petit donc, se pose immédiatement la question suivante : sur laquelle des deux autres piques le placer ? La vidéo ci-dessous discute de ce problème.

Récursion – Tours de Hanoï.
Vidéo produite par wandida.com – Intervenant : Christian Queinnec, édition : El Mahdi El Mhamdi – Creative Commons BY-NC-SA.

La récursion est très utilisée en informatique. Elle intervient dans les algorithmes, dans la résolution des problèmes esquissés ci-dessus. Elle intervient aussi dans les données, car leurs relations peuvent être représentées sous la forme d’arbre et un arbre est un tronc qui mène à des branches, branches qui elles-mêmes peuvent être vues comme des troncs menant à d’autres branches, etc. Ce sont ces intrigantes caractéristiques qu’explore le MOOC « Programmation récursive ».

Regardez bien autour de vous, la récursion est là !