(
课件网) 5.2 迭 代 与 递 归 （二） ———递 归 册 别：选择性必修1 学 科：高中信息技术（浙教版） 学习目标： 能理解递归的算法思想。 能合理选用数据结构，理清递归公式及结束条件，递归的递推与回归两个阶段。 能用自然语言、流程图、Python语言描述递归算法。 能掌握递归算法的一般设计思路。 能自觉应用递归算法，解决生活、学习中的问题。 引入：猜猜E娃娃有几个铜币？ 2 3 A B C D E 我比前一个娃娃少2个铜币！ 我比前一个娃娃少2个铜币！ 我比前一个娃娃少2个铜币！ 我比前一个娃娃少2个铜币！ 我有20个铜币！ 引入：俄罗斯套娃 2 3 相传俄罗斯民族有两家表亲相邻，表兄妹童年相伴长大，后来表兄远走它乡，由于思念家乡的表妹，每年做木娃娃，一年比一年做的娃娃大。数年后，他回到了家乡，将娃娃送给了表妹，后人模仿传称套娃，又叫吉祥娃娃。 递归算法基本思想 通过函数自己调用自己来实现，也就是在其定义中直接或间接调用自身的方法，称之为递归。 def tot(x): if x<=1: sum=1 else: sum=x+tot(x-1) return sum print(tot(3)) 直接调用 def t1(x): if x<=1: sum=1 else: sum=x+tot(x-1) return sum def tot(y): if y>20: s=0 else: s=y*t1(y) return s 间接调用 算一算:小猴子第一天摘了多少个桃子 找出规律 天 10 9 8 … 2 1 桃子数t 1 (t(10)+1)*2 (t(9)+1)*2 (t(3)+1)*2 (t(2)+1)*2 有一天小猴子摘若干个桃子,当即吃了一半还觉得不过瘾,又多吃了一个。第二天接着吃剩下桃子中的一半，仍觉得不过瘾又多吃了一个，以后小猴子都是吃尚存桃子一半多一个。到第10天小猴子再去吃桃子的时候，看到只剩下一个桃子。问小猴子第一天共摘了多少个桃子 能用递归算法解决问题的特征 天 10 9 8 … 2 1 桃子数t 1 (t(10)+1)*2 (t(9)+1)*2 (t(3)+1)*2 (t2)+1)*2 为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解中方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法。 当递归到达某个边界，如问题规模缩减为0或1时，能直接得解。 递归的两个条件 天 10 9 8 … 2 1 桃子数t 1 (t(10)+1)*2 (t(9)+1)*2 (t(3)+1)*2 (t2)+1)*2 if day==10: tot=1 elif day!=10: tot=(t(day+1)+1)*2 确定递归结束条件 确定递归公式 递归算法Python程序实现： 天 10 9 8 … 2 1 桃子数t 1 (t(10)+1)*2 (t(9)+1)*2 (t(3)+1)*2 (t(2)+1)*2 if day==10: tot=1 elif day!=10: tot=(t(day+1)+1)*2 确定递归结束条件 确定递归公式 def t(day): return tot print(t(1)) if day==10: tot=1 elif day!=10: tot=(t(day+1)+1)*2 递归算法的执行过程: 递推：将复杂的问题（规模为n)的求解递推出一些简单的问题（规模小于n）的求解。此阶段，必须有终止递推的情况。 回归：获得最简单情况的解后，逐级返回依次得到稍复杂问题的解。 天 10 9 8 … 2 1 桃子数t 1 (t(10)+1)*2 (t(9)+1)*2 (t(3)+1)*2 (t2)+1)*2 递推 回归 逐层调用，直到边界（递推） 代入计算，依次返回（回归） 课堂小练：说说递归实现过程 def tot(x): if x<=1: sum=1 else: sum=x+tot(x-1) return sum print(tot(3)) 调用自身 1 2 3 4 5 6 7 7 print(tot(3)) 1 def tot(3): 2 if x<=1 False 4 else: 5 sum=3+tot(2) 1 def tot(2): 2 if x<=1 False 4 else: 5 sum=2+tot(1) 1 def tot(1): 2 if x<=1 True 3 sum=1 (13)返回1 (14)返回3 课堂小练：表格形式展示递归实现过程 调用自身 执行(1)7 print(tot(3)) 计算tot(3) 计算tot(3) 执行5 sum=3+tot(2) 结果sum=3+3, return sum,返回6，调用tot(3)结束 计算tot(2) 5 sum=2+tot(1) 结果sum=2+1, return sum,返回3，调用tot(2)结束 计 ... ...
