上面两个例子实际上都用不着递归，只需简单的循环就可以解决。

这种递归到非递归的转换总是可行的，因为归根结底，计算机的机器语言并不支持递归，所以从某种意义上说，递归并非不可替代的。上述阶乘函数很容易转换，但并不是所有函数都这么容易。下面这个例子是由Edouard Lucas在1883年第一次提出的一个游戏，名为汉诺塔（Tower of Hanoi）。

该游戏有三根柱子：A、B、C。在A柱上有一摞按大小排列的盘子“塔”，最大的盘子在最底部，最小的盘子在最顶部（参见图 1.1 “汉诺塔的初始状态”）。

图 1.1. 汉诺塔的初始状态

游戏的目的是要将所有盘子从A移动到C，但要服从以下限制：每次只能移动一个盘子，任何盘子不能放在比自己小的盘子上。至于盘子的总数，不同的出题者会给出不同的值，但传统上是64个盘子。下面我们来试着解决该问题的一般形式，即n个盘子的情况。

考虑n个盘子中最大的那个盘子，它位于最底部。最初，最大的盘子位于A柱，我们要将它移动到C柱。如果A柱上还有其他盘子，那么必然在最大的盘子的上放，所以没办法直接移动最大的盘子。如果C柱上有其他盘子，就无法将最大的盘子移动到C柱，否则它就会压在其他的小盘子之上了。所以，如果要将最大的盘子从A移动到C，那么其他所有盘子必须都被移动到B上，并按照从小到大的顺序排列（参见图 1.2 “汉诺塔的一种中间状态”）。

图 1.2. 汉诺塔的一种中间状态

因此，要解决这个问题，需要先完成一个子问题：把除了最大的盘子之外的所有盘子从A移动到B。只有这样，才能将最大的盘子从A移动到C。最后，就可以将余下的盘子从B移动到C，这是另一个子问题。

幸运的是，在移动较小的盘子时，可以完全忽略最大的盘子，不管它在哪儿，都不会造成任何影响。这就意味着在移动较小的盘子时可以使用同样的逻辑。较小的一摞盘子的“塔”的底部是相对较大的盘子；只需将“塔”中的其他盘子移走，再将底部的盘子移动到正确的位置，最后将其余小盘子移动到它上边即可。那么，其余那些小盘子怎样移动呢？照旧。

最后需要考虑的问题就是怎样将只有一个盘子的一“摞”移动，其实它就是最小的盘子。这个问题已经微不足道，只需将最小的盘子放在需要的地方即可。我们知道它上面不会有任何东西（否则就违反规则了），还知道可以随时把它移动到任何地方，因为它是最小的，所以不可能把它放在比它还小的盘子上。

移动最初那一摞盘子塔的策略如下：

要将n个盘子从起点柱移动到终点柱，应当：

这个策略可以轻而易举地写成程序：

# hanoi(N, start, end, extra)
# 解决含有N个盘子的汉诺塔问题，其中最大的盘子为#N。
# 要将整个塔从'start'移动到'end'，使用'extra'
# 作为存放盘子的临时空间
sub hanoi {
  my ($n, $start, $end, $extra) = @_;
  if ($n == 1) {
    print "Move disk #1 from $start to $end.\n"; # 第1步
  } else {
    hanoi($n-1, $start, $extra, $end); # 第2步
    print "Move disk #$n from $start to $end.\n"; # 第3步
    hanoi($n-1, $extra, $end, $start); # 第4步
  }
}
			

该函数会打印出一系列的指令，表明如何移动塔。例如，要获得移动三个盘子的指令，只需这样调用：

hanoi(3, 'A', 'C', 'B');
			

输出结果为：

Move disk #1 from A to C.
Move disk #2 from A to B.
Move disk #1 from C to B.
Move disk #3 from A to C.
Move disk #1 from B to A.
Move disk #2 from B to C.
Move disk #1 from A to C.
			

如果想把移动盘子用图形来显示，而不是输出一行说明文字，可以用更巧妙的语句代替print。不过，只需稍稍动点脑筋，就可以把软件做得更灵活些——通过参数来指定输出的行为。不再硬性书写print，而是让hanoi()接收一个函数作为参数，每次hanoi()想要移动盘子时就调用它。这个函数可以输出说明文字，可以更新图形显示，或者做其他动作。传给该函数的参数为盘子的序号、移动的原点和移动的目标。代码几乎完全相同：

sub hanoi {
  my ($n, $start, $end, $extra, $move_disk) = @_;
  if ($n == 1) {
    $move_disk->(1, $start, $end);
  } else {
    hanoi($n-1, $start, $extra, $end, $move_disk);
    $move_disk->($n, $start, $end);
    hanoi($n-1, $extra, $end, $start, $move_disk);
  }
}
			

要想获得与原版同样的结果，可以这样调用hanoi()：

sub print_instruction {
my ($disk, $start, $end) = @_;
	print "Move disk #$disk from $start to $end.\n";
}

hanoi(3, 'A', 'C', 'B', \&print_instruction);
			

\&print_instruction这种写法可以生成一个代码引用（code reference），它是代表函数的一个标量。与其他类型的标量一样，可以将代码引用保存在一个标量变量中，或作为参数传递，也可以用该引用来调用它所代表的函数。调用方法为：

$code_reference->(arguments...);
			

这样即可用指定的参数调用函数。 ^[1] 代码引用通常称为coderefs。

传给hanoi()的那个代码引用称为回调函数（callback，因为调用者提供给hanoi()的这个函数，是在hanoi()需要的时候“回来调用”的。有时也把hanoi()函数的这个$move_disk参数称为钩子（hook），因为通过它可以方便地挂接其他功能。

有了通用的hanoi()函数，我们可以传进一个$move_disk函数，跟踪盘子的位置，并检查移动是否合法，就可以对该算法进行测试：

@position = ('', ('A') x 3); # Disks are all initially on peg A

sub check_move {
  my $i;
  my ($disk, $start, $end) = @_;
			

check_move()函数维护一个数组@position，用于记录每个盘子的当前位置。最初，所有盘子都位于A柱。这里假设只有三个盘子，所以设置$position[1]、$position[2]和$position[3]为"A"。由于没有零号盘子，所以$position[0]永远不会用到。每次hanoi()函数想要移动盘子时，就会调用check_move()。

if ($disk<1|| $disk > $#position) {
  die "Bad disk number $disk. Should be 1..$#position.\n";
}
			

这个检查并不重要，只是为了确保hanoi()没有移动不存在的盘子。

unless ($position[$disk] eq $start) {
	die "Tried to move disk $disk from $start, but it is on peg
	$position[$disk].\n";
}
			

这段代码检查hanoi()在移动盘子时，盘子的源位置是否与实际相符。如果源位置与check_move()记录的盘子当前位置不符，该函数就会产生错误。

for $i (1 .. $disk-1) {
  if ($position[$i] eq $start) {
    die "Can't move disk $disk from $start because $i is on top of it.\n";
  } elsif ($position[$i] eq $end) {
    die "Can't move disk $disk to $end because $i is already there.\n";
  }
}
			

这段检查代码最有意思。函数依次检查所有比hanoi()想要移动的那个盘子小的盘子，确保移动过程中没有小盘子的阻碍。第一个if判断确保所有小盘子都不在hanoi()要移动的盘子之上， 而第二个确保hanoi()不会把盘子放在小盘子上。

  print "Moving disk $disk from $start to $end.\n";
  $position[$disk] = $end;
}
			

最后，函数判断移动中没有任何错误，就输出一条信息，并调整@position数组，以反映盘子的新位置。

运行以下代码：

hanoi(3, 'A', 'C', 'B', \&check_move);
			

就会得到跟前面相同的结果，没有任何错误，说明hanoi()所做的动作都是正确的。

这个例子演示了一项十分有价值的技术，在今后的学习中我们会反复遇到——将函数的某一部分变成参数，去调用其他函数，而不是将动作直接写出来，可以让函数更加灵活。如果想让函数执行的动作稍有不同，如进行自动自检等，就会知道这种灵活性的好处。无需为函数书写一大堆乱七八糟的测试代码，只要把测试部分从主算法中分离出来即可。主算法尽量保持简洁，如果需要测试，只需给它传递不同的代码引用参数，即可启用或禁止运行时的自检。