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], [], []);
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?