0

I'm reading Douglas Crockford's 'JavaScript: The Good Parts'. In a small section devoted to recursion, he brings up a famous 'Tower of Hanoi' puzzle, and prezents 'trivially' simple recursive solution to it in JS.

Quote:

The Towers of Hanoi is a famous puzzle. The equipment includes three posts and a set of discs of various diameters with holes in their centers. The setup stacks all of the discs on the source post with smaller discs on top of larger discs. The goal is to move the stack to the destination post by moving one disc at a time to another post, never placing a larger disc on a smaller disc. This puzzle has a trivial recursive solution:

var hanoi = function (disc, src, aux, dst) {
    if (disc > 0) {
        hanoi(disc - 1, src, dst, aux);
        document.writeln('Move disc ' + disc +
                         ' from ' + src + ' to ' + dst);
        hanoi(disc - 1, aux, src, dst);
    }
 };

 hanoi(3, 'Src', 'Aux', 'Dst');

The output if the code is this:

Move disc 1 from Src to Dst

Move disc 2 from Src to Aux

Move disc 1 from Dst to Aux

Move disc 3 from Src to Dst

Move disc 1 from Aux to Src

Move disc 2 from Aux to Dst

Move disc 1 from Src to Dst

This is of course the correct sequence of movements to solve the puzzle, but to be honest, this recursive code seems like magic to me. I've been trying to break it into smaller parts and understand it, but it's hard.

  1. I do not get it why the first printed statement is "Move disc 1 from Src to Dst" when the hanoi function was called with disc argument set to 3 with an immediate extraction of 1 (which gives 2);
  2. If it became 1 initially, why did it rise to be 2 again in the second statement "Move disc 2 from Src to Aux" - I do not see any addition in there.

I'd be so much grateful if somebody explained the logic behind this small snippet so that I can finally grab recursion.

luqo33
  • 8,001
  • 16
  • 54
  • 107
  • Try to add a statement like `document.writeln('called with ' + disc + ', ' + src + ', ' + aux + ' and ' + dst);` in the first line of the function. Maybe you'll understand better then. – Bergi May 28 '15 at 21:00
  • Also someone asked a very similar question which may help: http://stackoverflow.com/questions/3742305/crockfords-hanoi-function-from-the-good-parts?rq=1 – Oliver Barnwell May 28 '15 at 21:01
  • There are quite a few questions already asked (and [a Wikipedia entry that explains the solution](http://en.wikipedia.org/wiki/Tower_of_Hanoi#Recursive_solution)), about this specific example. If you look at the question I've suggested this is a duplicate of - or at the list of 'related' questions (to the right of the question/comments), they should explain adequately. If, however, I'm wrong - and you can explain how I'm wrong - then please notify me and I'll (perhaps) reopen, unless someone else does so first. – David Thomas May 28 '15 at 21:02

0 Answers0