La fonction hanoi de Crockford (de "The Good Parts")

En ce moment, je lis le livre de Douglas Crockford, et les tours de la fonction hanoi sont un peu au dessus de ma tête. Même avec des informations sur la console, je ne pouvais pas vraiment comprendre ce qui se passe. Voici la fonction avec mes ajouts:

var hanoi = function (disc, src, aux, dst) { console.log(disc); console.log(src, dst); if (disc > 0) { hanoi(disc - 1, src, dst, aux); console.log('Move disc ' + disc + ' from ' + src + ' to ' + dst); hanoi(disc - 1, aux, src, dst); } } hanoi(3, 'Src', 'Aux', 'Dst'); 

Il en résulte ce qui suit:

3
Src Dst
2
Src Aux
1
Src Dst
0
Src Aux
Déplacer le disque 1 de Src vers Dst
0
Aux Dst
Déplacer le disque 2 de Src vers Aux
1
Dst Aux
0
Dst Src
Déplacer le disque 1 de Dst vers Aux
0
Src Aux
Déplacer le disque 3 de Src vers Dst
2
Aux Dst
1
Aux Src
0
Aux Dst
Déplacer le disque 1 de Aux vers Src
0
Dst Src
Déplacer le disque 2 de Aux vers Dst
1
Src Dst
0
Src Aux
Déplacer le disque 1 de Src vers Dst
0
Aux Dst

Et je suis perdu dès le début. À la ligne 6 des résultats, comment peut-il revenir de Src Aux à Src Dst?

Et comment le nombre de disques peut-il augmenter une fois qu'il a atteint 0, alors que la fonction ne s'appelle que par "disque-1"?

La confusion se pose parce que la représentation textuelle de la sortie n'est pas la meilleure façon de comprendre la récursivité. Le nombre de disques n'est pas en train de «monter», mais c'est hanoi(1) qui continue de fonctionner une fois que hanoi(0) est terminé.

J'ai créé un exemple modifié dans JSBin qui imprime la sortie d'une manière (plus) plus jolie avec des espaces. Seuls les "mouvements" font quelque chose, le reste des lignes ne sont que des appels récursifs pour résoudre des sous-problèmes plus petits afin de s'attaquer à l'ensemble du problème plus tard.

Vous pouvez également regarder cette applet Java qui illustre graphiquement l'utilisation de l'algorithme – cela pourrait être plus facile à comprendre.

Towers of Hanoi est un excellent exemple de la façon dont la récursivité peut simplifier un problème donné. L'idée est la suivante: vous devez déplacer N disques d'une pile source vers une pile de destination, un disque à la fois et vous ne pouvez jamais mettre un disque plus petit sur un disque plus grand. Vous pouvez utiliser une pile auxiliaire. Disons N = 10. Vous ne savez pas comment le résoudre. Mais vous pouvez rendre le problème plus simple (vous l'espérons):

 move 9 disks to the auxiliary stack, move the remaining (and largest!) disk to the destination stack, and move the 9 disks from the auxiliary stack to the destination stack 

Encore une fois, vous ne savez pas comment déplacer une pile de disque 9, mais ce n'est pas non plus un problème.

 move 8 disks from the auxiliary stack to the source stack, move the remaining disk to the destination stack (there are 2 disks now), and move the 8 disks from the source stack to the destination stack 

Répétez ceci jusqu'à ce que la pile que vous devez déplacer ne soit que 1 disque.

A propos du nombre de disques à nouveau: vous appelez la fonction de manière récursive pour les disques N-1, qui dans la fonction est affectée à N. Ce N n'existe que jusqu'à ce que la fonction se termine et revienne au niveau précédent. Ensuite, vous obtenez à nouveau l'ancienne valeur de N.