2

所以我们有经典的河内问题，我刚刚进入这个递归的东西，它是一个doozie！这是功能齐全的，但我只是不明白它是怎么回事！据我了解，对于任何 n，它将打印“从 +”到“+ thru”，这将在每次 n 接近 1 时发生。人们会认为在 n=1 时，代码会停止，然而我得到了“thru +”的打印输出到“+ to”（最后一个打印输出）。如果 n=1 是终止条件，我怎么可能“免费”获得最后一部分代码？

我还希望代码至少在每次迭代时执行最后一次打印输出，但没有！此外，这方面的示例总是包括两个递归调用，但只有一个就可以了！这到底是怎么回事？这段代码是如何一步一步执行的？我是否误解了一些关于递归方法的基本事实？（在 Eclipse 编译器上编译）。

 public static void hanoi(char from, char to, char thru, int n) {
if (n==1) {
  System.out.println(from + " going to " + to);
}  else {
  System.out.println (from + " going to " + thru);
  hanoi(from, to, thru, n-1);
  System.out.println (thru + " going to " + to);
}
  }
4

3 回答 3

0

我是否误解了一些关于递归方法的基本事实？

听起来你有。您似乎有这样的印象，即使您多次调用该方法，该方法也只退出一次。事实上，每次你点击这条线：

System.out.println (from + " going to " + thru); <-- this line
hanoi(from, to, thru, n-1);
System.out.println (thru + " going to " + to);

...您还必须在递归调用完成后的某个时刻点击后面的一行：

System.out.println (from + " going to " + thru);
hanoi(from, to, thru, n-1);
System.out.println (thru + " going to " + to);   <-- this line

n == 1是“终止条件”，因为它不进行额外的递归调用。但是，您的“if”语句中仍然有代码：

if (n==1) {
  System.out.println(from + " going to " + to);
}

此代码将作为最终条件的一部分运行，但不会hanoi再次调用该方法。但是，这只是递归调用的结束。在此之前每调用一次hanoi，堆栈上仍然有一个方法调用，这些方法调用需要完成。

  System.out.println (from + " going to " + thru);
  hanoi(from, to, thru, n-1);   <-- if `n-1` here was `1`, you'd still have to 
                                    complete the following line.
  System.out.println (thru + " going to " + to);
于 2014-04-06T21:36:57.770 回答
0

有人会认为在 n=1 时，代码会停止

这就是错误假设所在。守则没有停止。方法执行后 System.out.println(from + " going to " + to); 返回到调用它的地方。在你的情况下。这就是hanoi(from, to, thru, n-1);所谓的。然后它一直持续到方法的末尾，因此执行System.out.println (thru + " going to " + to); 然后它再次返回到它被调用的位置并再次继续直到方法体的末尾。这种情况一次又一次地发生，直到您第一次调用hanoi().

于 2014-04-06T21:45:11.333 回答
0

Hanoi 的目标是将所有片段从“from”带到“to”，这听起来有点傻，所以我们将“from”称为“left”，将“to”称为“right”。对于 n = 1，您只需将棋子从左侧直接移动到右侧，即可按照规则成功完成游戏。这就是为什么您会显示您提到的文本。

对于 n = 2，您必须将顶部的部分移动到中间，底部的较大部分向右移动，然后将较小的部分从中间向右移动。

在伪代码中，这读作：

put the left piece to the middle

put the (other) left piece to the right 
(note that the roles of middle and right 
have been switched in the call of the 
hanoi-method and n is now 1, so no more calls)

put the middle piece to the right
于 2014-04-06T21:45:54.890 回答