浙教版 (2019)选修1 数据与数据结构第五章 数据结构与算法5.2 迭代与递归优秀课件ppt

这是一份浙教版 (2019)选修1 数据与数据结构第五章 数据结构与算法5.2 迭代与递归优秀课件ppt，共30页。PPT课件主要包含了学习目标，引入俄罗斯套娃，递归算法基本思想，直接调用，间接调用，找出规律，递归的两个条件，递归算法的执行过程，调用自身，13返回1等内容，欢迎下载使用。

能理解递归的算法思想。
能合理选用数据结构，理清递归公式及结束条件，递归的递推与回归两个阶段。
能用自然语言、流程图、Pythn语言描述递归算法。
能掌握递归算法的一般设计思路。
能自觉应用递归算法，解决生活、学习中的问题。
引入：猜猜E娃娃有几个铜币？
A B C D E
我比前一个娃娃少2个铜币！
相传俄罗斯民族有两家表亲相邻，表兄妹童年相伴长大，后来表兄远走它乡，由于思念家乡的表妹，每年做木娃娃，一年比一年做的娃娃大。数年后，他回到了家乡，将娃娃送给了表妹，后人模仿传称套娃，又叫吉祥娃娃。
通过函数自己调用自己来实现，也就是在其定义中直接或间接调用自身的方法，称之为递归。
def tt(x): if x<=1: sum=1 else: sum=x+tt(x-1) return sumprint(tt(3))
def t1(x): if x<=1: sum=1 else: sum=x+tt(x-1) return sum
def tt(y): if y>20: s=0 else: s=y*t1(y) return s
算一算:小猴子第一天摘了多少个桃子?
有一天小猴子摘若干个桃子,当即吃了一半还觉得不过瘾,又多吃了一个。第二天接着吃剩下桃子中的一半，仍觉得不过瘾又多吃了一个，以后小猴子都是吃尚存桃子一半多一个。到第10天小猴子再去吃桃子的时候，看到只剩下一个桃子。问小猴子第一天共摘了多少个桃子?
能用递归算法解决问题的特征
为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解中方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法。当递归到达某个边界，如问题规模缩减为0或1时，能直接得解。
if day==10: tt=1
elif day!=10: tt=(t(day+1)+1)*2
递归算法Pythn程序实现：
def t(day): return ttprint(t(1))
递推：将复杂的问题（规模为n)的求解递推出一些简单的问题（规模小于n）的求解。此阶段，必须有终止递推的情况。
回归：获得最简单情况的解后，逐级返回依次得到稍复杂问题的解。
逐层调用，直到边界（递推）代入计算，依次返回（回归）
课堂小练：说说递归实现过程
1 2 3 4 5 6 7
7 print(tt(3))1 def tt(3):2 if x<=1 False4 else:5 sum=3+tt(2)1 def tt(2):2 if x<=1 False4 else:5 sum=2+tt(1)1 def tt(1):2 if x<=1 True3 sum=1
课堂小练：表格形式展示递归实现过程
（1）有明确的结束递归的边界条件（终止条件）及终止时的边界值。（2）函数的描述中包含其本身。
课堂实践：用递归算法求 n 的阶乘
利用递归算法求n的阶乘（n!=1×2×…n-1×n）。由数学知识可知，n阶乘的递归定义为：它等于n乘以n-1的阶乘，即n！=n*(n-1)!,并且规定0和1的阶乘为1。设函数fac(n)=n!，则fac(n)可表示为：
1 n=0或n=1n*fac(n-1) n>0
函数fac←n*fac(n-1)
用递归算法求 n 的阶乘程序实现:
def fac(n): if n<= 1: return 1 else: return n * fac(n - 1)
#结束递归的边界条件（终止条件）
#结束递归的终止时的边界值
x=int(input())print(fac(x))
3、编写程序,并上机调试
1、分解成规模较小的同类型问题。
n!=n*(n-1)!
2、用递归函数替代多重循环。
3、解决本来就是用递归形式定义的问题。
#3、递归结束条件n<2
def fx(n): if n<2: （1） else: （2） return fprint（fx(10))
用递归算法求裴波那契数列为：1，1，2，3，5，8，13 ……
#5、递归表达式，自己调用自己
f=fx(n-1)+fx(n-2)
一个楼梯有n阶，上楼可以一步上一阶，也可以一步上二阶。要求：编写一个程序，输入一个正整数n(表示楼梯阶数)，输出共有多少种不同的走法可以到达第n阶。
2.程序设计并调试：
def fx(n):if n == 1 r n == 2:return nelse:return fx(n-1)+fx(n-2)n=int(input("台阶数量:"))print(“台阶走法:”,fx(n))
#3、递归结束条件n<=2
台阶走法迭代程序：n=int(input("台阶数量："))a=1;b=2fr i in range(3,n+1): c=a+b a=b b=cif n==1 r n==2: print(n)else: print(c)
台阶走法递归程序：def fx(n):if n == 1 r n == 2:return nelse:return fx(n-1)+fx(n-2)n=int(input("台阶数量:"))print(“台阶走法:”,fx(n))
思考：递归程序一般结构：
def fx(n): #递归函数if n == 1 r n == 2: #结束递归的边界条件return n #结束递归的值else:return fx(n-1)+fx(n-2) #递归表达式（调用自己）
1 2 3 4 5
汉诺塔游戏： 教材P124
为了将n个圆盘从A柱经过B柱移动到C柱，可建立如下模型：
将n-1个圆盘从A柱经过C柱移动到B柱
将A柱中剩下的一个圆盘移动到C柱
将n-1个圆盘从B柱经过A柱移动到C柱
得出关键点：注意最下面的圆盘
（1）定义一个实现圆盘移动的函数mve。如将n个圆盘从A柱经过B柱移动到C柱，可调用函数mve(n, a, b, c)，其中，n表示A柱上的圆盘个数，a、b、c分别表示A柱、B柱、C柱。（2）将n-1个圆盘从B柱经过A柱移动到C柱，可以分解成如下递归调用：mve(n-1, a, c, b)a→cmve(n-1, b, a, c)（3）当n=1时，直接移动圆盘，递归结束。
根据算法，得到的程序及测试效果如下：
算法思想 算法描述
递归算法的两个条件和两个阶段
递归算法的数学原理与注意事项
对自己的表现进行客观的评价，并思考后续完善的方向。（3=优秀，2=一般，1=仍需加油）
1.求最大公约数：早在公元前300年左右，欧几里得就在他的著作《几何原本》中给出了高效的解法——辗转相除法。 辗转相除法的方法是用较大的数X除以较小的数Y，得到余数Z 如果余数为0，则较小数Y就是两者的最大公约数。例如：33和9 的最大公约数就是9与6的最大公约数3以下程序#号划线处代码为（ ）A.a B. gcd(b,a%b) C. gcd(b,a//b) D. gcd(b,a)
def gcd(a,b): if a%b==0: return b else: return ## m,n=map(int,input().split())Print(gcd(m,n))
2. def zh(n): if n<=1: f='1' else: f=zh(n//2)+str(n%2) return fprint(zh(18))该程序段运行后的输出值为( )A、10100 B、10010 C、11010D、11000