Re:Thinking About Recursion
by justinpombrio on Wednesday March 08, 2017 @08:32PM
(#13825961)
> The thing I find fascinating about this solution is that it doesn't even require the rule that you can't place larger discs on smaller discs
It had better. If you're allowed to put larger disks on smaller disks, you can solve towers of Hanoi in linear time. Call the rods A, B, and C: the goal is to move the stack from A to C. First flip the stack upside down, one disk at a time, from A to B. Then do that again, from B to C. The stack is now upright on C, after 2n moves.
(In contrast, the real problem requires O(2^n) moves.)
It had better. If you're allowed to put larger disks on smaller disks, you can solve towers of Hanoi in linear time. Call the rods A, B, and C: the goal is to move the stack from A to C. First flip the stack upside down, one disk at a time, from A to B. Then do that again, from B to C. The stack is now upright on C, after 2n moves.
(In contrast, the real problem requires O(2^n) moves.)