资源简介

(共19张PPT)
5.2.2递归
递归算法
现在，我们把问题反过来思考
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=__________________
____________________
n=n // base
return ans
x=int(input("请输入x："))
y=int(input("请输入y："))
print(convert(x,y))
n %base
ans= convert_s[x] + ans
递归算法——综合应用
为了防止黑客恶意破解密码、机器恶意注册或刷票等不良行为,很多网络平台使用验证码作为一种通行方式。小明给自己的网站平台设计了如下验证码功能:首先计算机随机生成一个[1,100000]范围内的整数作为验证码,用户通过计算该整数各位数字的和并输入验证,只有验证通过才能正常登录。例如,若计算机产生的随机数为21304,则用户只有输入10(2+1+3 +0+4=10)才能正常登录。
递归算法——综合应用
【算法分析】
该验证码功能需要从随机数x中分解出各位数字并求和。由于随机数x的位数不确定,而任何整数x的个位数一定可以通过x%10得到，剩下的(x//10)可以采用递归算法进行分解。通过函数fenjie(x)先将x的各位数字分解并存入数组ans,再求得和sumx,最后将sumx与用户输入的信息进行比对,输出响应的提示信息，请完善以下代码。
递归算法——综合应用
import random
def fenjie(x):
if x<10:
ans.append(x)
else:
ys=x%10
____________
fenjie(x)
ans.append(ys)
x=random.randint(1,100000)
print("随机产生的整数为:",x)
y=int(input("请输入你的运算结果:"))
ans=[]
fenjie(x)
sumx=0
for i in ans:
___________
if _______________:
print("验证通过!")
else:
print("输入错误!")
x=x//10
sumx+=i
sumx==y
课堂小结
递归的必要条件
递归的适用情况
递归的定义
函数的递归调用是指一个函数在它的函数体内，直接或间接地调用它自身，称为递归调用。这种函数称为递归函数。
确定递归条件
寻找递归出口
问题在规模小时能够直接得出答案
可以通过同一套规则转化为比该问题更为简单的子问题。
练一练
1.递归算法的函数调用时，处理参数和返回地址通常使用的
数据结构是（ ）
A.数组
B.队列
C.栈
D.链表
C
练一练
2.楼梯上有8级台阶，从下开始往上走，每次可以走一步或者两步，自定义函数fg可以计算走完n级台阶有多少种走法。实现对应功能
的Python程序如下：
def fg(n):
if n==1:
return 1
elif n==2:
return 2
else:
return fg(n-1)+fg(n-2)
Print(‘走完8级台阶的方法共有’，fg(8)，‘种’)
则走完这8级台阶的走法有（ ）
A.34种 B.35种 C.36种 D.37种
A
THANK YOU
Speaker :wps powerpoint

展开更多......

收起↑