5.2.2递归 课件-2022-2023学年浙教版（2019）高中信息技术选修1

5.2.2递归 1 递归算法 现在，我们把问题反过来思考 f(5)=f(4)*5 f(4)=f(3)*4 f(3)=f(2)*3 f(2)=f(1)*2 f(1)=f(0)*1 递推 问题逐渐缩小 回归 大问题的解决中嵌套着与原问题相似的规模较小的问题。 这种解决问题的方式在计算机科学中称为递归，通过函数自己调用自己来实现，即一个函数在其定义中直接或间接调用自身的一种方法。 递归算法 1.大问题能分解成结构相似且规模较少的问题，这些小问题的阶可以方便地构造出大问题的解； 2.当递归到达某个边界时，当递归到达某个边界，如问题规模缩减为0或1时，能直接得解。这个边界被称为递归出口。 ·能采用递归算法解决的问题特征 因此，在设计递归算法时，要满足两个条件： 确定递归公式和递归结束条件。 递归算法 1（n=0） n*f(n-1)（n>0） f(n) 5！= 5 * 4！ 4！= 4 * 3！ 3！= 3 * 2！ 2！= 2 * 1！ 1！= 1 * 0！ 0！= 1 递推：分解问题 回归：代值求解 任务一：利用递归思想设计一个函数f，用来计算5的阶乘 def f(n): if n==0: ___________ else: ___________ return f f=1 f=n*f(n-1) 算法时间复杂度为： O(n) 递归算法 递归程序的执行过程 1.在递推阶段，把较复杂的问题的求解递推到一些简单问题的求解。必须要有终止递推的情况。 2.在回归阶段，当获得最简单情况的解后，逐级返回依次得到稍复杂问题的解。 递归算法 1*fac(0) 2*fac(1) 3*fac(2) 4*fac(3) 5*fac(4) fac(1) fac(2) fac(3) fac(4) fac(5) 通过不断的调用自己缩小问题规模，进而求解。 空间复杂度大 用栈实现递归： 递归算法 迭代：由旧值不断推出新值的过程。它包括三个方面： ①确定迭代变量； ②建立迭代关系式； ③控制迭代过程，使程序能够停止下来。 递归：是一种缩小问题规模，进而构造出整个问题解的思想方法。 ①递推 ②回归 迭代难点：建立正确的迭代公式，通常要借助循环语句。 递归难点：思想比较难以理解，递归程序的效率相对不高。 辨析迭代与递归： 递归算法——汉诺塔游戏 汉诺塔游戏 汉诺塔游戏的装置是一块铜板，上面有三根针，其中最左侧一根针上放着从大到小的n个圆盘。 游戏的目标是把所有的圆盘从最左侧一根针上移动到最右侧一根针上，中间一根针作为过渡。 游戏规定每次只能移动一个圆盘，并且大盘子不能压在小盘子上面。 递归算法——汉诺塔游戏 汉诺塔游戏 启始针A 过渡针B 目标针C 一个盘子: 二个盘子: 三个盘子呢？ n个盘子呢？ 将n-1个盘子从A柱经过C柱移动到B柱 将A柱中剩下的一个盘子移动到C柱 将n-1个盘子从B柱经过A柱移动到C柱 n-1个看成一个整体 A->C 2号：A->B 1号：A->C 2号：B->C 递归算法——汉诺塔游戏 将n-1个盘子从A柱经过C柱移动到B柱 将A柱中剩下的一个盘子移动到C柱 将n-1个盘子从B柱经过A柱移动到C柱 【设计算法】 1.定义一个实现盘子移动的函数move。 如将n个盘子从A柱经过B柱移动到C柱，可调用函数move(n, a, b, c)， 其中，n表示A柱上的盘子个数，a、b、c分别表示A柱、B柱、C柱。 2.当n=1时，直接移动盘子，递归结束。 move(n-1, a, c, b) move(1, a, b, c) move(n-1, b, a, c) 递归算法——汉诺塔游戏 def move(n, a, b, c): if ____________: print(a, "--->", c) else: move(n - 1, a, c, b) move(1, a, b, c) ____________ a = int(input("请输入A柱盘子的个数：")) print(f"把{a}个盘子全部移动到C柱子的顺序为：") move(a, "A", "B", "C") n == 1 move(n-1, b, a, c) 递归算法——进制转换 编写程序，输入两个正整数 x,y(y<=l6),实现将十进制数x 转换为十六进制y输出。 迭代程序 def convert(n,base): convert_s = "0123456789ABCDEF" ans="" while n>0: x=__________________