我正在学习 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?
最佳答案
如果你把它打印成一棵树,你会得到这样的东西:
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, ...)
关于c++ - 了解 c++ 代码 : Tower of Hanoi using Recursion,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54609056/