理解 C++ 代码：使用递归的汉诺塔

Question

我正在学习 c++ 中的递归，但被以下用于解决汉诺塔问题的 c++ 代码难住了。

void Hanoi(int m, string start, string middle, string end){
    cout << "m is equal to: " << m << endl;
    if(m == 1){
        cout << "Move Disc " << " from " << start << "  to " << end << endl;
    }
    else{
        Hanoi(m-1,start,end,middle);
        cout << "Move disc " << m << " from " << start << " to " << end << endl;
        Hanoi(m-1,middle,start,end);
    }
}
int main(){
    int discs = 3;
    Hanoi(discs, "start","middle","end");

}

代码输出结果如下：

m is equal to: 3
m is equal to: 2
m is equal to: 1
Move Disc  from start  to end
Move disc 2 from start to middle
m is equal to: 1
Move Disc  from end  to middle
Move disc 3 from start to end
m is equal to: 2
m is equal to: 1
Move Disc  from middle  to start
Move disc 2 from middle to end
m is equal to: 1
Move Disc  from start  to end

我的一般问题是我不明白递归是如何工作的。为什么 m 在执行 "if" 语句之前转到 1？ m怎么变回2？

Answer 1

如果你把它打印成一棵树，你会得到这样的东西：

main
  |--> hanoi(3, ...)
  |      |
  |      |--> hanoi(2, ...)
  |      |     |
  |      |     |--> hanoi(1, ...)
  |      |     |--> hanoi(1, ...)
  |      |<----|
  |      |--> hanoi(2, ...)
  |      |     |
  |      |     |--> hanoi(1, ...)
  |      |     |--> hanoi(1, ...)
  |      |<----|
  |<-----|
  |

对于 hanoi(m, ...) 的每次调用，它将继续调用 hanoi(m - 1, ...) 两次，除非 m == 1。在第一次调用中，它将再次调用 call hanoi(m - 1, ...) ...直到 m 为 1。

因此当 m 为 2 时向后移动它将连续调用 hanoi(1, ...) 两次：

   hanoi(2, ...)
      hanoi(1, ...)
      hanoi(1, ...)

当 m 为 3 时，它将连续调用 hanoi(2, ...) 两次，因此：

hanoi(3, ...)
   hanoi(2, ...)
      hanoi(1, ...)
      hanoi(1, ...)
   hanoi(2, ...)
      hanoi(1, ...)
      hanoi(1, ...)

Answer 2

这条线索应该对你有帮助，如果没有，那么你总是可以通过谷歌搜索找到更多线索"Tower of Hanoi recursion program trace"

您还可以在 https://javabypatel.blogspot.com/2015/12/tower-of-hanoi.html

找到该算法的工作原理

Answer 3

让我们从输出的第一部分开始： m is equal to: 3 m is equal to: 2 m is equal to: 1

Hanoi函数首先是这样调用的：Hanoi(3).
由于在这种情况下 m != 1，我们将再次调用 Hanoi(m-1)。这将产生上面的输出。我们现在在这个函数中有 3 个层次。

自 m == 1 以来，我们现在将看到以下输出： Move Disc from start to end.

现在，我们退出最深的函数并返回到函数调用堆栈的第 2 层。现在我们输出： Move disc 2 from start to middle.

Answer 4

您的目标是将所有磁盘移动到另一个地方。

要解决这个难题，您需要将塔从位置 1 移动到位置 2。
为此，您需要将最大的圆盘从位置 1 移动到位置 2。
为此，位置 2 需要为空，所有其他磁盘需要位于位置 3（作为大小为 m-1 的塔）。
因此您需要解决大小为 m-1 的拼图（将大小为 m-1 的塔从位置 1 移动到位置 3）。这是第一个递归调用。
现在您可以将最大的圆盘从位置 1 移动到位置 2。这是递归函数调用之间的输出。
现在需要将m-1大小的塔从位置3移动到位置2
所以你需要再次解出m-1大小的拼图（将m-1大小的塔从位置3移到位置2）。这是第二次递归函数调用。

唯一可以不用递归解决的问题是将大小为 1 的塔移动到另一个地方，因为顶部不能有任何磁盘，您可以在任何其他磁盘的顶部移动。这就是 m 必须为 1 才能执行 if 语句的原因。

理解 C++ 代码：使用递归的汉诺塔

Understanding c++ Code: Tower of Hanoi using Recursion

c++

recursion

towers-of-hanoi