Re: Recursion: the Towers of Hanoi problem

[Anonymous Monk]

Too bad people introduce the Towers of Hanoi, and then stop when they have introduced recursion. Because there's much more to discover. For instance that disks move in simple cycles, with half the disks moving in one direction, the other half in another. And that given the move number, one can calculate which disk needs to be moved based on the binary respresentation of the move number. Here's an interative solution based on those facts:

$*=shift;
for($_=1;$_<=$*;$_++){$_[$_]=[split$,,(($*%2)xor($_%2))?ABC:ACB]}
for($_=1;$_<2**$*;$_++){
  $-=1+length((sprintf("%b",$_)=~/(0*)$/)[0]);
  printf"Move disk %d from pole %s to pole %s\n",$-,@{$_[$-]}[0,1];
  push@{$_[$-]},shift@{$_[$-]}
}