河内塔递归java

这是我使用递归解决河内塔的Java代码：

/**here is a stack of N disks on the first of three poles (call them A, B and C) and your job is to move the disks from pole A to pole B without ever putting a larger disk on top of a smaller disk.*/ public class Hanoi { public static void main(String[] args) { playHanoi (2,"A","B","C"); } //move n disks from position "from" to "to" via "other" private static void playHanoi(int n, String from , String other, String to) { if (n == 0) return; if (n > 0) playHanoi(n-1, from, to, other); System.out.printf("Move one disk from pole %s to pole %s \n ", from, to); playHanoi(n-1, other, from, to); } } 

我把打印方法的地方重要吗？ 另外，我可以这样做：

  playHanoi(n-1, from, to, other); playHanoi(n-1, other, from, to); System.out.printf("Move one disk from pole %s to pole %s \n ", from, to); 

Answer 1

以这种方式解决Tower of Hanoy问题Tower of Hanoy是定义了如何完成工作的策略。 而你的代码：

  playHanoi(n-1, from, to, other); System.out.printf("Move one disk from pole %s to pole %s \n ", from, to); playHanoi(n-1, other, from, to); 

基本上定义了你喜欢的策略，

1. 将n-1个磁盘从“从” （源塔）移动到“其他” （中间塔）。
2. 然后将第n个磁盘从“从” （源塔）移动到“到” （目标塔）。
3. 最后将n-1个磁盘从“其他” （中间塔）移动到“到” （目标塔）。

你的prinf基本上是第二步。

现在，如果你编写这样的代码：

  playHanoi(n-1, from, to, other); playHanoi(n-1, other, from, to); System.out.printf("Move one disk from pole %s to pole %s \n ", from, to); 

那你基本上是这样做的：

1. 将n-1个磁盘从“从” （源塔）移动到“其他” （中间塔）。
2. 然后将n-1个磁盘从“其他” （中间塔）移动到“到” （目标塔）。

3. 最后将第n个磁盘从“从” （源塔）移动到“到” （目标塔）。

   在此策略中，在执行第二步（将所有n-1个磁盘从“其他”移动到“到” ）后，第3步变为无效（将第n个磁盘从“从”移动到“到” ）！ 因为在Tower of Hanoy你不能把一个更大的磁盘放在一个更小的磁盘上！

因此，选择第二个选项（策略）会导致您采用无效策略，这就是为什么您不能这样做的原因！

Answer 2

确实很重要。 在递归调用之后的任何内容都将在递归之后执行（以及之前的任何内容），因此您可能会发现输出是无意义的顺序。

请记住，函数调用之后的语句在函数返回之前不会执行。