资源简介

(共30张PPT)
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)结束
计算tot(1)； 执行2 if x<=1 （True） 3 sum=1 return sum 调用返回1，tot(1)调用结束
调用
调用
调用
返回
返回
返回
递归实现要点:
（1）有明确的结束递归的边界条件（终止条件）及终止时的边界值。
（2）函数的描述中包含其本身。
def tot(x):
if x<=1:
sum=1
else:
sum=x+tot(x-1)
return sum
print(tot(3))
def t(day):
if day==10:
tot=1
elif day!=10:
tot=(t(day+1)+1)*2
return tot
print(t(1))
课堂实践：用递归算法求 n 的阶乘
1、抽象建模
利用递归算法求n的阶乘（n!=1×2×…n-1×n）。由数学知识可知，n阶乘的递归定义为：它等于n乘以n-1的阶乘，即n！=n*(n-1)!,并且规定0和1的阶乘为1。设函数fac(n)=n!，则fac(n)可表示为：
fac(n)=
1 n=0或n=1
n*fac(n-1) n>0
课堂实践：用递归算法求 n 的阶乘
2、设计算法
开始
n<=1
输入n
输出n!
函数fac←n*fac(n-1)
结束
N
Y
函数fac←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、解决本来就是用递归形式定义的问题。
课堂小练：（填空）
#1、如求第10项
#2、递归函数fx
#3、递归结束条件n<2
def fx(n):
if n<2:
（1）
else:
（2）
return f
print（fx(10))
用递归算法求裴波那契数列为：1，1，2，3，5，8，13 ……
f(n)=
1 n<=1
f(n-1)+f(n-2) n>=2
#4、递归结束值
#5、递归表达式，自己调用自己
f=1
f=fx(n-1)+fx(n-2)
1
2
3
4
5
6
7
课堂小练：
一个楼梯有n阶，上楼可以一步上一阶，也可以一步上二阶。要求：编写一个程序，输入一个正整数n(表示楼梯阶数)，输出共有多少种不同的走法可以到达第n阶。
2.程序设计并调试：
f(n)=
1 n=1
2 n=2
f(n-1)+f(n-2) n>=3
用递归编程实现：
def fx(n):
if n == 1 or n == 2:
return n
else:
return fx(n-1)+fx(n-2)
n=int(input("台阶数量:"))
print(“台阶走法:”,fx(n))
#1、如求第台阶走法
#2、递归函数fx
#3、递归结束条件n<=2
#4、递归结束值
#5、递归表达式，自己调用自己
1
2
3
4
5
6
7
比较迭代与递归：
迭代 递归
初始值 终止值
迭代表达式 递归表达式
终止条件 终止条件
循环实现 递归函数实现
台阶走法迭代程序：
n=int(input("台阶数量："))
a=1;b=2
for i in range(3,n+1):
c=a+b
a=b
b=c
if n==1 or n==2:
print(n)
else:
print(c)
台阶走法递归程序：
def fx(n):
if n == 1 or n == 2:
return n
else:
return fx(n-1)+fx(n-2)
n=int(input("台阶数量:"))
print(“台阶走法:”,fx(n))
思考：递归程序一般结构：
def fx(n): #递归函数
if n == 1 or n == 2: #结束递归的边界条件
return n #结束递归的值
else:
return fx(n-1)+fx(n-2) #递归表达式（调用自己）
1
2
3
4
5
汉诺塔游戏： 教材P124
1. 抽象与建模
为了将n个圆盘从A柱经过B柱移动到C柱，可建立如下模型：
将n-1个圆盘从A柱经过C柱移动到B柱
将A柱中剩下的一个圆盘移动到C柱
将n-1个圆盘从B柱经过A柱移动到C柱
得出关键点：注意最下面的圆盘
2.设计算法
（1）定义一个实现圆盘移动的函数move。如将n个圆盘从A柱经过B柱移动到C柱，可调用函数move(n, a, b, c)，其中，n表示A柱上的圆盘个数，a、b、c分别表示A柱、B柱、C柱。
（2）将n-1个圆盘从B柱经过A柱移动到C柱，可以分解成如下递归调用：
move(n-1, a, c, b)
a→c
move(n-1, b, a, c)
（3）当n=1时，直接移动圆盘，递归结束。
汉诺塔游戏： 教材P124
if(n == 1):
print(a,"->",c)
return
move(1, a, b, c)
汉诺塔游戏： 教材P124
3.编写程序
拓展学习：
递归与栈
程序 测试效果
def move(n, a, b, c): if(n == 1): print(a,"->",c) return move(n-1, a, c, b) move(1, a, b, c) move(n-1, b, a, c) move(3, "A", "B", "C") A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
根据算法，得到的程序及测试效果如下：
课堂小结
递归算法的概念
算法思想 算法描述
递归算法的两个条件和两个阶段
递归算法的数学原理与注意事项
程序实现
学习评价
对自己的表现进行客观的评价，并思考后续完善的方向。（3=优秀，2=一般，1=仍需加油）
评分项 自我评价
能计算小猴摘桃并总结递归算法的基本思想 3 2 1
掌握递归算法的两个条件和两个阶段 3 2 1
能自主学习教材并用自然语言、Python语言描述递归算法 3 2 1
能够编程实现斐波那契数列、阶乘的递归实现 3 2 1
掌握递归算法的设计思路，理解其数学原理和注意事项 3 2 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)
B
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 f
print(zh(18))
该程序段运行后的输出值为( )
A、10100 B、10010 C、11010 D、11000
B
课后作业
3.有如下数列a1,a2,a3,…的定义如下:
a1=1,a2=1 ,…,an =3an-1+2an-2(n>2)。为求该数列的第n项值,现利用递归算法实现,Python代码如下,请在划线处填入合适的代码。
def yuan(x):
if x<=2 :
return ①
else :
②
n=int(input(“n=“))
print(yuan(n))
1
② return 3*yuan(x-1)+2*yuan(x-2)

展开更多......

收起↑