资源简介

(共17张PPT)
三、 递归算法及其应用
第五章　数据结构与算法
知识过关
(一)递归算法
1. 递归算法的概念
为求解规模为n的问题,设法将它分解成规模较小的问题,然后从这些小问题的解中方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,这种解决问题的方式在计算机科学中称为递归。当递归到达某个边界时,能直接得解。
递归算法的基本思想是把规模较大的、较难解决的问题变成规模较小的、容易解决的同一问题,规模较小的问题又变成规模更小的问题,当问题小到一定程度时,可以直接得出它的解,从而得到原来问题的解。
2. 利用递归算法解决问题的关键步骤
(1)抽象建立递归模型,确定递归公式。
(2)确定临界条件(即递归结束条件)。
例如,下面的自定义函数f调用自身,因此属于递归算法,用自定义函数实现,也称为递归函数。
def f(n):　　　　　　　　　　 #自定义函数f
　　if n == 1:
　　　 s = 1
　　else:
　　　 s = n * f(n － 1)+ 1　　　 #函数调用自身,属于递归调用
　　　 return s　　　　　　　　　 #返回函数值s
k=int(input())　　　　　　　　 #主程序
print(f(k))　　　　　　　　　　　 #调用函数f
3. 递归算法的实现要点
递归调用必须是有限的。进行算法描述时,必须设置相关的控制条件,使其成为有限的。这可以通过条件语句来实现,即只有在设定的条件成立时递归才继续,否则终止递归。可见,构成递归必须满足以下条件:
(1)有明确的结束递归的边界条件(又称终止条件)以及结束时的边界值。
(2)函数的描述中包含其本身,即能用递归形式表示,且递归终止条件明确。
4. 递归算法的设计方法
当所求解的问题难于直接求解时,首先,把问题分解成若干个难度较小、较容易求解的子问题,子问题与原问题具有类同的结构。若子问题能够直接求解,则解之;如果子问题仍不能直接求解,将每个子问题再分解成若干个更简单的子问题,直到分解出的子问题能够很容易地求解或解已知,这是实现递归的模板。然后,设计递归出口(即结束递归的边界条件),当满足出口条件时,递归函数不能再调用自己,必须返回一个确定的值。
(二)迭代和递归的联系和区别
1. 递归
程序调用自身的编程技巧称为递归,是函数自己调用自己。由于递归会引起一系列的函数调用,并且有可能会有一系列的重复计算,递归算法的执行效率相对较低。
2. 迭代
迭代是利用变量的原值推算出变量的一个新值。如果递归是自己调用自己的话,那么迭代就是A不停地调用B。
理论上,迭代和递归在时间复杂度方面是等价的(不考虑函数调用开销和函数调用产生的堆栈开销),但实际上递归效率比迭代低,由于递归需要系统堆栈,所以空间消耗要比非递归代码大很多。
一般情况下,递归算法都可以转换为迭代算法。递归中一定有迭代,但是迭代中不一定有递归,大部分递归和迭代可以相互转换。递归的优点是易理解、容易编程,缺点是递归带来了大量的函数调用,导致效率较低。迭代虽然相对于递归效率高,但缺点是不容易理解,编写复杂问题时比较困难。
典例精选
【例1】 (2023·浙江1月选考)定义如下函数:
def f(n):
　　if n<3:
　　　return n
　　return f(n－1)+f(n－3)
执行语句v=f(5),函数f被调用的次数是(　　)
A. 1 B. 5
C. 7 D. 15
【解析】 本题考查递归算法知识。观察自定义函数可知,当参数n大于等于3时,继续两次递归调用(参数为n－1和n－3),反之结束递归直接返回值。题干执行的语句中参数值为5较小,故可以直接模拟并分析计算过程:①f(5)=f(4)+f(2),调用函数f两次;②f(4)=f(3)+f(1),调用函数f两次;③f(3)=f(2)+f(0),调用函数f两次;再加上v=f(5)本身调用的一次,得到答案7。C正确。
C
【例2】 阶乘n!=1×2×3×…×n,利用递归思想可以转化为n!=(n－1)!×n。实现阶乘功能的Python代码如下,请在画线处填入合适的代码。
def factorial(n):
　　if n==1:
　　　　return 1
　　else:
　　　　return ①__________________________
n = int(input())
print("阶乘的结果是:",②_______________)
【解析】 本题考查递归算法知识。①n不为1时,转换为n－1的自身,这样就实现了递归算法。②此处需要将实际参数n的值代入函数factorial(),从而经过递归运算得到实际的函数值。递归调用因为占用了大量的内存和时间,付出代价高昂,从而导致效率低下的问题。Python语言的递归深度一般设为1000。
n * factorial(n－1)
factorial(n)
【例3】 (2023·浙江6月选考)定义如下函数:
　def f(a,s):
　　　if a>=s:
　　　　　return a
　　　else:
　　　　　return f(a+1,s－a)
执行语句k = f(6,21)后,k的值为(　　)
A. 6 B. 7
C. 8 D. 9
【解析】 本题考查递归算法及自定义函数知识。观察自定义函数f(a,s)可知:当参数a≥s时(即递归结束条件),返回值为a;否则递归调用f(a+1,s－a)。执行语句k=f(6,21),模拟计算过程如下:第一次调用函数f(6,21);由于未达到递归结束条件,第二次调用函数f(7,15);未达到递归结束条件,第三次调用函数f(8,8),满足递归结束条件a≥s,返回值为a,得到答案8,C正确。
C
【例4】 爬楼梯问题:有n级台阶,如果一次只能上一级或两级台阶,求一共有多少种上楼梯的方法。请编写Python程序,并使用自定义函数对该过程进行模拟。
(1)如果楼梯只有一级台阶,那么爬楼梯只有1种可能(0到1),即f(1)=1。
(2)如果楼梯有两级,可以有两种方法,一种是0到1到2,另一种是直接0到2,故f(2)=2。
(3)如果楼梯有三级,若第一步爬一级楼梯的话(0到1),则剩下的可能是f(2):即1到2到3,或1直接到3;若第一步爬两级台阶的话(0到2),剩下的可能是f(1),也就只有一种可能,即2到3,所以f(3)= f(1)+ f(2)=3;
(4)如果楼梯有四级,若第一步爬一级楼梯的话,则剩下的可能是f(3);若第一步爬两级楼梯的话,则剩下的可能是f(2),所以f(4)= f(2)+ f(3)。
同理可知,f(n)= f(n－1)+ f(n－2)(n≥3)。
综上所述,爬n级楼梯的方法总数f(n)的一般形式为:
实现上述功能的Python代码如下，请在画线处填入合适的代码。
def louti(x):　　　　　　　　　#变量x为形式参数
　　if x == 1:
　　　　s = 1
　　elif x == 2:
　　　　s = 2
　　elif x >= 3:
　　　　s = ①__________________________________　
　　return s
n = int(input("n="))
print(②__________)　#变量n为实际参数
louti(x － 1) + louti(x － 2)
louti(n)
【解析】 本题是斐波那契数列的实现,考查递归算法和自定义函数来模拟一个简单的游戏。①此处需要调用自定义函数louti,注意形式参数的使用。②此处主要利用递归思想解决函数返回值。
自我检测
1. 下列关于迭代算法和递归算法的说法,错. 误. 的是(　　)
A. 使用递归算法时,必须有一个明确的递归结束条件,称为递归出口
B. 一般来说,迭代算法效率较低,而递归算法效率较高
C. 递归中一定有迭代,但迭代中不一定有递归
D. 通常情况下,迭代算法和递归算法可以相互转换
【解析】 本题考查迭代算法和递归算法的特征。一般来说,迭代算法效率较高,而递归算法比较占用空间,程序运行效率较低,B符合题意。
B
2. 在计算机内实现递归算法时,所需要的数据结构是(　　)
A. 数组 B. 栈
C. 队列 D. 链表
【解析】 栈的特点是先进后出,符合递归算法的思想,即在计算机内实现递归算法时使用栈数据结构,B正确。
B
3. 有如下Python程序段:
def f(x):
　　if x==1:
　　　　return 1
　　else:
　　　　return x*f(x－1)
s=0
for i in range(1,6):
　　s+=f(i)
print(s)
执行该程序段后,变量s的值为(　　)
A. 33 B. 34
C. 154 D. 153
【解析】 通过自定义函数的关键代码“x*f(x－1)”,发现该函数是通过递归算法计算x的
阶乘。后面的循环是把1 到5 的阶层进行累加,1!+2!+3!+4!+5!=1+2+6+24+120=153,D正确。
D

展开更多......

收起↑