python-3.x - 递归问题中使用不同参数多次调用的函数

Question

我对编程还很陌生，我刚刚被介绍给递归的概念。我遇到了著名的河内塔问题。以下是我正在关注的课程中的那个人如何解决它：

def printmove(fr,to):
   print('move from'+ str(fr)+'to'+str(to))


def Towers(n,fr,to,spare):
   if n == 1:
      printmove(fr,to)
   else:
      Towers(n-1,fr,spare,to)
      Towers(1,fr,to,spare)
      Towers(n-1,spare,to,fr)
Towers(4,"P1","P2","P3")

我不明白的是（很可能它很明显，但我无法理解它）它如何知道何时传递给第二个递归调用 Towers(1,fr,to,spare)？

标签： python-3.xrecursiontowers-of-hanoi

Answer 1

它如何知道何时传递给第二个递归调用 Towers(1,fr,to,spare)？

实际上，这些递归函数之间的执行顺序是由这个控制块决定的；

if n == 1:
      printmove(fr,to)

正如你所看到的，一旦n变量达到值1，else 语句将不会再次被访问，这就是函数执行将结束的原因（递归将中断）。一旦结束，程序流程将继续执行下一行代码，即Towers(1,fr,to,spare). 对于您的具体示例，您已将整数值4传递给您的函数调用Towers(4,"P1","P2","P3")，因此我将尝试说明您的程序的执行顺序以更清楚；

1. n = 4，执行else语句，else语句的第一行代码为Towers(4 -1,fr,spare,to)，递归树增加一个新的函数执行
2. n = 3，执行else语句，else语句的第一行代码为Towers(3 -1,fr,spare,to)，在递归树中增加一个新的函数执行
3. n = 2，执行else语句，else语句的第一行代码为Towers(2 -1,fr,spare,to)，递归树增加一个新的函数执行
4. n = 1，如果语句被执行，被执行printmove(fr,to)，递归被中断。
5. 树上所有先前的递归函数执行都按倒序死亡（最后添加到递归树 -> 第一次死亡）。
6. 现在，唯一有效的函数执行是我们的第一次调用，Towers(4,"P1","P2","P3")因为n = 4
7. 程序流程继续下一行代码，即Towers(1,fr,to,spare)
8. 它继续在该逻辑中流动，直到最后一个递归函数调用终止。

因此，如果该代码中没有if-else逻辑，则递归Towers(n-1,fr,spare,to)将永远不会中断并开始无限递归。