递归问题中使用不同参数多次调用的函数

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,空闲的）？

Answer 1

在递归中，每个函数都有自己的状态。因此，当 Towers(n-1,fr,spare,to) 函数运行时，它会递归调用自身，每次调用都会将参数值减 1。此函数满足 n==1 条件后，其递归结束，然后递归开始 Towers(1,fr,to,spare) 并继续。

为了更好地理解这个过程，添加一些额外的打印语句并观察值的变化。

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


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

我不会在这里发布答案，但基本上第一个函数运行直到 n 从 4 变为 1，然后第二个运行，依此类推。

Answer 2

how does it know when to pass to the second recursive call 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")，因此我将尝试说明您的程序的执行顺序，以便更清楚；

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

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

递归问题中使用不同参数多次调用的函数

Function called multiple times with different parameters in recursion problem

python-3.x

recursion

towers-of-hanoi