Tours de Hanoï - récursivité

Bonjour à tous!

Alors voilà, j'ai du mal à comprendre une fonction récursive écrite en Caml, qui a pour but de résoudre le problème des tours de Hanoï.

Le jeu des tours de Hanoï consiste en une plaquette sur laquelle sont plantées trois tiges (A,B,C). Sur la première de ces tiges (A) sont enfilés, dans l'état initial du jeu, n disques dont les diamètres sont strictement décroissants (le plus grand est en bas) et le but du jeu est de transférer les n disques de la tige de départ (A) vers la tige but (C) en respectant les 3 règles suivantes :

-toutes les tiges peuvent être utilisées comme intermédiaire;
-on ne peut transférer qu'un disque à la fois;
-on n'a pas le droit de poser un grand disque sur un petit disque.

On introduit pour cela la fonction deplace qui, pour deplace x y, renvoie l'affichage de l'instruction "déplacer le disque au sommet de x vers le sommet de y".

Voici donc la fonction qui me pose problème, dont je n'arrive pas à comprendre le fonctionnement, où n est le nombre de disques, d la tige de départ, i la tige intermédiaire, b la tige but :

let rec hanoï n d i b =
if n=1
then déplace d b
else begin
hanoï (n-1) d b i;
déplace d b;
hanoï (n-1) i d b
end ;;


Ceci s'adresse principalement à ceux qui connaissent déjà le langage Caml, car je pense que le fonctionnement de cette fonction, même en connaissant le langage, n'est pas très facile à comprendre.

Quelqu'un peut-il m'expliquer ce fonctionnement?

Merci.

Salut à toi Alpha !

Ben, je ne connais absolument pas le langage Caml...Mais, je vais tenter ma chance !
J'interprète ce code de la manière suivante :
Hypothèse : cette fonction est en mesure de déplacer k disques de la tige représentée par le deuxième argument (d) vers la tige représentée par le quatrième argument (b) en utilisant éventuellement la tige représentée par le troisième argument (i), à la condition que ces disques soient tous plus petits que les disques éventuellement déjà posés sur les tiges i et b, de manière à pouvoir tous les y poser au besoin - ceci pour tout k <= (n-1). Puisque l'on ne peut déplacer qu'un disque à la fois, il va de soi que pour déplacer le plus grand de ces n disques (celui qui est tout en dessous), on doit d'abord déplacer les n-1 disques situés au dessus de celui-là. Et comme, lorsque le plus grand disque sera dégagé, on voudra le poser sur la tige b, il faut donc d'abord déplacer les (n-1) disques du dessus de la tige d à la tige i : c'est ce qu'on fait en appelant "hanoï (n-1) d b i" (la tige b peut bien servir de tige auxilliaire pour l'instant). Ensuite on déplace le plus grand disque de la tige d à la tige b. Enfin, on déplace à nouveau les n-1 disques préalablement déplacés sur i, de i à b et bien entendu, la tige d peut alors jouer le rôle de tige intermédiaire (avec l'appel : hanoï (n-1) i d b).
Ainsi, il est établi que cette fonction est en mesure de déplacer k disques de la tige représentée par le deuxième argument (d) vers la tige représentée par le quatrième argument (b) en utilisant éventuellement la tige représentée par le troisième argument (i), à la condition que ces disques soient tous plus petits que les disques éventuellement déjà posés sur les tiges i et b, de manière à pouvoir tous les y poser au besoin - ceci pour tout k <= n.

Comme la fonction fonctionne évidemment pour n=1, la récurrence est complète.

Merci beaucoup pour cette réponse, Quidam! A vrai dire, je reviendrai pour te dire ce que j'en ai compris, car je n'ai pas le temps de m'y consacrer tout de suite. Je vais imprimer ta réponse et la regarder, et ce soir ou demain je répondrai.

Amicalement, Alpha

Je reviens pour te dire que je suis tout à fait d'accord avec ton interprétation du fonctionnement de la fonction. Maintenant, ça me semble très clair et très simple!

Grâce à tes explications :happy3:

À ton service ! Ravi d'avoir contribué...