资源简介

(共17张PPT)
Phthon编程------ 5 递归算法
微项目5
用递归算法优化程序
学习活 过程与目标 核心问题
1、跟踪递归的运行过程，通过数据跟踪实验，了解递归思想的基本思路和运行过程，如何将大问题拆解为同类的小问题
2、探究递归算法的优势，通过案例对比递归与迭代算法的不同，探究递归算法的优势，递归的优势是什么
学习目标
汉诺塔(Hanoi Tower)是根据印度古老传说形成的一个问题:
有A、B、C三根柱子，A柱上有n个穿孔圆盘(n>1)，盘的尺寸由下到上依次变小，要求把所有的圆盘移动到C柱。
游戏规定，可以将圆盘临时放在B柱，但大盘不能叠在小盘上面，并且每次只能移动一个圆盘。
汉诺塔问题
用递归策略编程
5
4
3
2
1
A
B
C
为汉诺塔游戏设计一个自定义函数，函数名称为hanoi，包括四个输人参数，依次为挑战层数n、起止柱begin、中转柱temp和终点柱 end，相关的Python代码如图所示。
程序代码中:
① 如果层数n=1，满足终止条件，打印圆盘移动信息。
② 如果层数n>1，连续三次递归调用，依次实现n-1层挑战、1层挑战、n-1层挑战。
#!/usr/bin/env python3# 汉诺塔递归求解函数
def hanoi(n,begin,temp,end):
if n==1:
#打印圆盘移动信息
print(“移动”,begin,"-->",end)
else:
# 完成挑战只需三步
hanoi(n-1,begin,end,temp)
hanoi(1,begin,temp,end)
hanoi(n-1,temp,begin,end)
#函数调用示例
n=5
print(“-- 汉诺塔”，n“层挑战操作步骤 --”)
hanoi (n, “A", “B",“C")
递归函数的规范形式如下:
def函数名([参数列表]):
if 条件表达式: #终止条件
语句
return 值(或表达式) #可省略
else: #递归条件
包含自身函数名([参数列表])的语句
递归算法的条件
递归算法解决问题的核心：递归函数的构建。程序运行时，由于递归函数不断调用自身，如果没有设置终止条件，递归调用会形成无限循环。
规范的递归函数必须由两个条件组成:
终止条件
递归条件
符合终止条件终止函数调用
符合递归条件则函数继续调用自身。
活动1 跟踪递归的运行过程
解决问题：
假设一个自然数n，累乘是将从1到n的所有自然数相乘，乘积m=1x2x3x4x5x…xn。
递归过程：
下面通过一个累乘过程的数据跟踪检测小实验，来体会递归算法是如何工作的
递归算法是一种反复调用(引用)自身求得结果的算法，使用递归算法通常需要定义递归函数(直接或间接调用自身的函数)。
递归只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量，因此在很多函数编程中习惯使用递归来实现循环。
通过将问题重复分解为同类的子问题来解决问题的方法称为递归，它是一种描述问题和解决问题的基本方法。
日常生活中，以相似方法重复事物的现象被称作递归(如照镜子)，而在计算机领域，递归是程序调用自身的编程技巧。
例如n=7 m=1x2x3x4x5x…xn 递归的实现过程
#!/usr/bin/env python3
def fact(n): #自定义函数
print("当前n=",n) #跟踪显示n，可省略
if n==1: #终止条件
return 1 #结束递归
else: #递归条件
f=n*fact(n-1) #调用递归
print("当前乘积:",f) #跟踪显示累乘的积
return f #返回乘积
#主程序
print("m=",fact(7)) #调用递归
当前n= 7
当前n= 6
当前n=5
当前n= 4
当前n= 3
当前n= 2
当前n= 1
当前乘积: 2
当前乘积: 6
当前乘积: 24
当前乘积: 120
当前乘积: 720
当前乘积: 5040
m= 5040
累
乘运
行
结
果
递归算法的程序实现
fact(7)
7* fact(6)
7*(6*fact(5))
7*(6*fact(5*fact(4)))
7*(6*fact(5*fact(4*fact(3))))
7*(6*fact(5*fact(4*fact(3*fact(2)))))
7*(6*fact(5*fact(4*fact(3*fact(2*fact(1))))))
递归算法求解过程
讨论
1.递归中，自定义函数如何深入展开
2.数据运算顺序有何特点
解决问题：
著名的斐波那契数列，又称为“兔子数列”，因以兔子繁殖为例而得名。
某饲养场引进一对刚出生的新品种兔子，这种兔子第2个月长为成年兔，从第3个月起一对成年兔每个月都新生一对幼兔。每对兔子都经历这样的出生、成长、繁殖过程。假设所有兔子都不死，到第12个月时，该饲养场共有兔子多少对
活动2 探究递归算法的优势
#!/usr/bin/envpython3
# 幼兔和成年兔第i月当月的数量分别用a、b表示
a=1 #幼兔第1月当月的数量(单位:对)
b=0 # 成年兔第1月当月的数量(单位:对)
print("第 %d 个月饲养场兔子共计 %d 对"%(1,a+b))
n=12 #总月数
#从第2月到第n月进行迭代计算
for i in range(2.n+1):
t=b # 先把上月成年兔数量存一下
b=a+b #本月成年兔数量=上月幼兔数量+成年兔数量
a=t #本月新生幼兔数量=上月成年免数量
print("第 %d个月饲养场兔子共计 %d 对“%(i.a+b))
1. 迭代算法
迭代算法的核心是通过将迭代表达式不断重复执行，用变量的旧值推出新值，直到完成指定计算。
兔子数列形如1,1,2,3,5,8,13,21,34……
如果设f(i)为该数列的第i项，当i大于2时，f(i)=f(i-1)+f(i-2)。
通过定义递归函数完成数列的推算，代码示例如图所示。
2.递归算法——完成程序设计
#!/usr/bin/env python3
def f(n):
if n<=2:
return 1
else:
return f(n-1)+f(n-2) #第n月兔子为前两个月之和
for i in range(1,13):
print("第",i,"月兔的数量是",f(i))
对比两种解决兔子繁殖问题的程序代码可以发现
迭代算法使用的是循环结构;
而递归算法通过调用自身，变成简单问题求解，再由简单问题逐步“回归”得出复杂问题的答案。
迭代算法 与 递归算法 的对比
返回第6页
课堂小结
什么是递归算法？
如何构造递归函数？
迭代算法的优势是什么？
递归算法的优势是什么？

展开更多......

收起↑