0

I am befuddled by the recursive solution for Towers of Hanoi that decrements a disc argument on each recursive call without starting at the initiated value of disc nor ending the recursion after disc amount of calls.

Shouldn't disc - 1 reach the value 0 after disc amount of calls? Where is the magician's hand in this elegant trick? Why does each new call seem to be working on its own disc value rather than the original argument?

function hanoi(disc, src, dst, aux) {
  if (disc === 0) {
    var disk = src.pop();
    dst.push(disk);
  } else {
    hanoi(disc-1, src, aux, dst);
    var disk = src.pop();
    dst.push(disk);
    hanoi(disc-1, aux, dst, src);
  }
}

hanoi(10, [10, 9, 8, 7, 6, 5, 4, 3, 2, 1], [], []);
Daniel A. White
  • 187,200
  • 47
  • 362
  • 445
Friendly-Robot
  • 1,124
  • 14
  • 24
  • Do you know what a local variable is? Each call *does* get its own `disc` variable. – user2357112 Feb 04 '16 at 19:54
  • Okay, I buy that. But take the recursive factorial solution for example, why doesn't `n * factorial(n - 1)` factor `n` as **0** in the beginning and why does its recursive call decrement `n` in a linear way with its own localized variable of `n - 1` ? – Friendly-Robot Feb 04 '16 at 20:08
  • There's a fuller explanation of the recursion [here](http://stackoverflow.com/questions/1223305/tower-of-hanoi-recursive-algorithm). This covers part of what you asked. – Prune Feb 12 '16 at 21:22
  • Thanks, @Prune! I've finally earned the authority to up-vote so I've casted mine for what it's worth! Really appreciate it. – Friendly-Robot Feb 13 '16 at 00:58

1 Answers1

1

Factorial is linear recursion. Towers of Hanoi is a double recursion: each deeper level requires 2 recursions for each time its called. Thus, moving N disks requires 2^N - 1 total moves.

The algorithm reads something like this:

If this is the largest disk: move it to the destination peg; now we're done.

Otherwise: move the next disc down to the third peg; move this one to the destination peg; move that next disk to the destination peg;

It's this "otherwise" part that takes two calls for one.

Does that clarify anything for you?

Prune
  • 76,765
  • 14
  • 60
  • 81
  • Oh, I see those two new local `disc` variables now! They are decrementing in their own local scopes, and when one reaches `disc === 0`, it returns with pushing the `src` value to the `dst' peg which is `aux` in the first call and then the second recursive call ends with pushing the `src` value which is from the `aux` peg to the `dst` peg. **One last question** though, @Prune and thank you for your explanation by the way, it is quite suffice. Shouldn't the first recursive call to `hanoi(disc-1, src, aux, dst)` start again from the top and call itself again, how does it run the code below it? – Friendly-Robot Feb 05 '16 at 01:31
  • It calls itself to move **disc** to the aux peg. When those 2^(disc-1)-1 moves are done, control returns to do the pop-push that moves **disc**. Then it continues, another recursive call to do the second half of the work: moving all the smaller disks from the aux peg to sit on the one we just moved. – Prune Feb 05 '16 at 20:56