c++ - 了解 c++ 代码 : Tower of Hanoi using Recursion

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, ...) 的每次调用，除非 m == 1，否则它将继续调用 hanoi(m - 1, ...) 两次。在第一次调用中，它将调用再次调用 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, ...)