鱼C论坛

 找回密码
 立即注册
查看: 1570|回复: 2

递归

[复制链接]
发表于 2023-10-7 15:45:33 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x

def moveDisk(fp, tp):
    print("moving disk from %d to %d\n" % (fp, tp))
def moveTower(height, fromPole, toPole, withPole):
    if height >= 1:
        moveTower(height-1, fromPole, withPole, toPole)
        moveDisk(fromPole, toPole)
        moveTower(height-1, withPole, toPole, fromPole)
moveTower(3,1,3,2)

在执行完moveTower(3,1,3,2)后,会执行moveTower(2,1,3,2),然后再执行moveTower(1,2,3,2),不是会无限循环吗,moveDisk(fromPole, toPole)
       moveTower(height-1, withPole, toPole, fromPole)代码就执行不了,但事实上时可以执行的,这是为什么,这段代码的运行可不可以用图表表示出来,会比较好理解
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-10-7 15:46:48 | 显示全部楼层
这段代码使用递归来实现汉诺塔问题的解决方案。递归是一种通过调用自身的方式来解决问题的方法。

在这段代码中,moveTower函数接受四个参数:height(汉诺塔的高度)、fromPole(起始柱子)、toPole(目标柱子)和withPole(辅助柱子)。首先,函数会检查height是否大于等于1,如果是,则继续执行递归调用。

在递归调用中,函数会先将height减1,然后将起始柱子fromPole作为参数传递给下一次递归调用的withPole参数。这样,递归调用会将从起始柱子移动到辅助柱子,并且高度减1。

然后,函数会调用moveDisk函数,将起始柱子fromPole上的一个盘子移动到目标柱子toPole上。

最后,函数再次进行递归调用,将辅助柱子withPole作为参数传递给下一次递归调用的fromPole参数。这样,递归调用会将从辅助柱子移动到目标柱子,并且高度减1。

这个过程会一直重复,直到height为1时递归终止。整个过程中,每次递归调用都会移动一个盘子,并且高度减1,直到所有盘子都从起始柱子移动到目标柱子。

因此,这段代码不会无限循环。每次递归调用都会逐渐减小问题的规模,直到达到终止条件。

关于图表表示,可以使用树状图来表示递归调用的过程。树的根节点表示初始调用,每个子节点表示一个递归调用。在每个节点上,可以标记对应的参数值和执行的操作。通过观察树的结构,可以更好地理解递归调用的过程和顺序。

希望这个解释对你有帮助!如果还有其他问题,请随时提问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-10-7 15:48:57 | 显示全部楼层
在执行递归函数时,Python 会为每个函数调用创建一个新的局部命名空间和一个新的调用堆栈。当递归函数调用自身时,它会将新的参数传递给函数,并在新的命名空间和调用堆栈中执行新的函数。每个递归函数调用都是独立的,因此它们不会相互干扰或导致无限循环。

在执行 moveTower(3,1,3,2) 时,首先会将 height 参数设置为 3,然后调用 moveTower 函数。在该函数中,如果 height>=1,则会执行三行代码:

[/code]
moveTower(height-1, fromPole, withPole, toPole)
moveDisk(fromPole, toPole)
moveTower(height-1, withPole, toPole, fromPole)
[/code]

第一行代码调用 moveTower(2, 1, 2, 3) 并将 height 参数设置为 2。在这个新调用中,又会执行三行代码,包括调用 moveTower(1, 1, 3, 2) 和调用 moveDisk(1, 2)moveTower(1, 1, 3, 2)height 参数设置为 1,并调用 moveDisk(1, 3)。由于 height 等于 1,这个调用将不会产生任何额外的递归调用,因此程序将执行 moveDisk(1, 3)moveTower(1, 2, 3, 1),然后返回到先前的递归调用。

接下来,递归调用 moveTower(2, 1, 2, 3)height 参数再次设置为 2,并调用 moveTower(1, 1, 2, 3)moveDisk(1, 2)moveTower(1, 1, 2, 3) 不会产生任何额外的递归调用,因此将执行 moveDisk(1, 2)moveTower(1, 3, 2, 1)

回到最初的递归调用,现在它将运行 moveTower(2, 2, 3, 1)。这个递归调用将 height 参数设置为 2,并调用 moveTower(1, 2, 1, 3)moveDisk(2, 3)moveTower(1, 2, 1, 3)height 设置为 1,并调用 moveDisk(2, 1)。这个递归调用完成后,程序将继续执行 moveDisk(2, 3)moveTower(1, 1, 3, 2)

最后,回到最初的递归调用,现在它将运行 moveTower(3, 2, 3, 1)。这个递归调用将 height 参数设置为 3,并调用 moveTower(2, 2, 1, 3)moveDisk(3, 1)moveTower(2, 2, 1, 3)height 设置为 2,并调用 moveTower(1, 2, 3, 1)moveDisk(2, 1)。这个递归调用完成后,程序将继续执行 moveDisk(3, 1)moveTower(2, 3, 1, 2)

通过上述过程可以看出,在递归函数中,每次递归调用都会独立创建自己的命名空间和调用堆栈,不会相互干扰或导致无限循环。

关于图表表示:可以使用一个栈来追踪函数调用和返回。当 moveTower() 被调用时,将 heightfromPoletoPolewithPole 压入栈中。每当递归调用函数时,也将这些参数压入栈中。当函数返回时,从栈中弹出参数并恢复先前的状态。

球一个最佳答案谢谢啦!这对我非常重要!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-24 08:59

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表