python算法学习:递归算法

2022-08-0710:24:02数据结构与算法Comments760 views字数 1288阅读模式

前面学习过递归函数,递归函数采用的就是递归算法,前面我们通过最常见的菲波那切数列去学习了递归函数,这一节我们再来详细了解一下递归算法。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

1. 递归算法文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

递归算法(英语:recursion algorithm)在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题,因此它是计算机科学中十分重要的一个概念,递归算法有三个特点:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

1) 递归的过程一般通过函数或者子过程来实现。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

2) 递归算法在它内部来直接或者间接的调用自身的算法。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

3) 递归算法就是把规模大的问题转换为规模小的问题,然后递归调用函数来求解的过程。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

递归算法也有几点需要注意的事项,在前面递归函数中我们也提到过,分别是:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

1) 递归是在函数本身调用函数本身。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

2) 递归的效率比较低,如果有时间限制不建议使用。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

3) 递归过程中需要有一个明确的结束条件,即递归出口。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

2. 汉诺塔问题文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

汉诺塔问题也是一道十分经典的算法题目。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

问题描述如下:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

汉诺塔是一种古老的游戏。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

一共3个柱子,标号为1,2,3。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

1号柱子有从大到小一共n个盘子。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

每次移动最上方的一个盘子,可以移动到其他的柱子。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

任何一个盘子,都不能叠在比它更小的盘子的上方。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

请把盘子从1号柱子,全部移动到3号柱子。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

起始:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

python算法学习:递归算法文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

移动到这样:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

python算法学习:递归算法文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

现在,给出了n个盘子,请你描述一下用最短次数移动的过程。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

我们先来分析这种三个盘子的时候的移动方式为:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

python算法学习:递归算法 ->python算法学习:递归算法文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

python算法学习:递归算法->python算法学习:递归算法文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

python算法学习:递归算法->python算法学习:递归算法文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

python算法学习:递归算法->python算法学习:递归算法文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

代码如下:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  = 1
def move(n,fr,to):
    global i
    print('这是第%d步:把%d号盘子从%s移动到%s'%(i,n,fr,to))
    += 1
def hanoi(n,a,b,c):
    if == 1:
        move(1,a,c)
    else:
        hanoi(n-1,a,c,b)
        move(n,a,c)
        hanoi(n-1,b,a,c)
if __name__ == '__main__':
    = int(input('输入A上面盘子的数量:'))
    print('移动开始')
    hanoi(n,'A','B','C')

我们输入3来测试一下移动步骤与上图是否对应:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

1
2
3
4
5
6
7
8
9
输入A上面盘子的数量:3
移动开始
这是第1步:把1号盘子从A移动到C
这是第2步:把2号盘子从A移动到B
这是第3步:把1号盘子从C移动到B
这是第4步:把3号盘子从A移动到C
这是第5步:把1号盘子从B移动到A
这是第6步:把2号盘子从B移动到C
这是第7步:把1号盘子从A移动到C

通过结果我们可以看到和图中所示一致,注意代码中的hanoi(n,a,b,c)表示为把A根柱子上的n个盘子通过B柱子移动到C柱子上,hanoi(n-1,1,3,2)然后就要执行hanoi(n-1,2,1,3),主要是通过这个递归函数来完成柱子的移动。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

 3. 总结文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

递归思想在我们的学习中经常会用到,如何巧妙的运用递归,可以参考一下前面递归函数中的内容。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/26674.html

  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/26674.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定