java - 汉诺塔，工作但不应该

Question

所以我们遇到了经典的 Hanoi 问题，我刚刚开始研究这个递归问题，这真是太棒了! 这是完全正常的，但我只是不明白它怎么可能!据我了解，对于任何 n，它都会打印“from +”到“+ 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);
}
  }

Answer 1

Have I misunderstood some basic fact about recursive methods?

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

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);