递归算法及其应用一轮复习课件-2025-2026学年浙江省高三信息技术选择性必修一

递归算法及其应用 1 知识过关 2 (一)递归算法 1. 递归算法的概念 为求解规模为n的问题,设法将它分解成规模较小的问题,然后从这些小问题的解中方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,这种解决问题的方式在计算机科学中称为递归。当递归到达某个边界时,能直接得解。 递归算法的基本思想是把规模较大的、较难解决的问题变成规模较小的、容易解决的同一问题,规模较小的问题又变成规模更小的问题,当问题小到一定程度时,可以直接得出它的解,从而得到原来问题的解。 3 2. 利用递归算法解决问题的关键步骤 (1)抽象建立递归模型,确定递归公式。 (2)确定临界条件(即递归结束条件)。 例如,下面的自定义函数f调用自身,因此属于递归算法,用自定义函数实现,也称为递归函数。 f(n)= 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 4 3. 递归算法的实现要点 递归调用必须是有限的。进行算法描述时,必须设置相关的控制条件,使其成为有限的。这可以通过条件语句来实现,即只有在设定的条件成立时递归才继续,否则终止递归。可见,构成递归必须满足以下条件: (1)有明确的结束递归的边界条件(又称终止条件)以及结束时的边界值。 (2)函数的描述中包含其本身,即能用递归形式表示,且递归终止条件明确。 4. 递归算法的设计方法 当所求解的问题难于直接求解时,首先,把问题分解成若干个难度较小、较容易求解的子问题,子问题与原问题具有类同的结构。若子问题能够直接求解,则解之;如果子问题仍不能直接求解,将每个子问题再分解成若干个更简单的子问题,直到分解出的子问题能够很容易地求解或解已知,这是实现递归的模板。然后,设计递归出口(即结束递归的边界条件),当满足出口条件时,递归函数不能再调用自己,必须返回一个确定的值。 5 (二)迭代和递归的联系和区别 1. 递归 程序调用自身的编程技巧称为递归,是函数自己调用自己。由于递归会引起一系列的函数调用,并且有可能会有一系列的重复计算,递归算法的执行效率相对较低。 2. 迭代 迭代是利用变量的原值推算出变量的一个新值。如果递归是自己调用自己的话,那么迭代就是A不停地调用B。 理论上,迭代和递归在时间复杂度方面是等价的(不考虑函数调用开销和函数调用产生的堆栈开销),但实际上递归效率比迭代低,由于递归需要系统堆栈,所以空间消耗要比非递归代码大很多。 一般情况下,递归算法都可以转换为迭代算法。递归中一定有迭代,但是迭代中不一定有递归,大部分递归和迭代可以相互转换。递归的优点是易理解、容易编程,缺点是递归带来了大量的函数调用,导致效率较低。迭代虽然相对于递归效率高,但缺点是不容易理解,编写复杂问题时比较困难。 6 典例精选 7 【例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)的一般形式为: 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,注意形式参数的使用。②此处主要利用递归思想解决函数返回值。 自我检测 14 1. 下列关于迭代算法和递归算法的说法,错. 误. 的是(　　) A. 使用递归算法时,必须有一个明确的递归结束条件,称为递归出口 B. 一般来说,迭代算法效率较低,而递归算法效率较高 C. 递归中一定有迭代,但迭代中不一定有递归 D. 通常情况下,迭代算法和递归算法可以相互转换 【解析】 本题考查迭代算法和递归算法的特征。一般来说,迭代算法效率较高,而递归算法比较占用空间,程序运行效率较低,B符合题意。 B 15 2. 在计算机内实现递归算法时,所需要的数据结构是(　　) A. 数组 B. 栈 C. 队列 D. 链表 【解析】 栈的特点是先进后出,符合递归算法的思想,即在计算机内实现递归算法时使用栈数据结构,B正确。 B 16 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 17 必备知识练 18 1. 如下程序的功能为使用递归的方法快速计算xn。画线处的代码是(　　) def fun(x,n): 　　if n==1: 　　　　return x 　　t=fun(____________________)  　　if n%2==1: 　　　　return x*t*t 　　else: 　　　　return t*t A. n//2,x B. n/2,x C. x,n//2 D. x,n/2 【解析】 本题考查递归算法及Python程序实现。由if条件分支代码可知,此处先递归计算x^(n//2),即t=fun(x,n//2),如果n是偶数,则返回x*t*t,如果n是奇数,则直接返回t*t,C正确。 C 19 2. 对于任意非空字符串s,下面两个程序段输出结果相同,则方框处应填入的代码是(　　) D def f(s,t): 　　if t >= len(s)－2: 　　　　return s[t] 　　return f(s,t＋2) ＋ s[t] print(f(s,0)) r = "" n = len(s) for i in range(0,n,2): 　　　　　　　　 print(r) A. r = s[n－i]＋r B. r = r＋s[n－i－1] C. r = r＋s[i] D. r = s[i]＋r 20 【解析】 本题考查递归和递推。左边的程序段是一个递归函数,其逻辑是:如果 t >= len(s) － 2,返回字符串 s 的第 t 个字符,否则递归调用 f(s, t ＋ 2),并将结果与 s[t] 拼接。因此函数 f(s, 0) 的作用是从字符串 s 的第 0 个字符开始,每隔一个取一个字符(偶数索引),并将这些字符逆序拼接成结果字符串。右边的程序段则是采用循环递推的方式,索引从 0 开始遍历字符串,且每次步进 2(跳过一个字符),再拼接成结果字符串。因索引必须是偶数且逆序拼接结果字符串,而n的奇偶性不确定,D正确。 3. 有如下Python程序: def fib(n): 　　if n == 1 or n == 2: 　　　　s = 1 　　else: 　　　　s = fib(n－1)＋ fib(n－2) 　　return s n = int(input()) print(fib(n)) 若输入n的值为8,则输出是(　　) A. 5 B. 8 C. 13 D. 21 【解析】 本题考查递归算法的程序实现。在自定义函数中,又出现调用自定义函数本身,由此判断程序使用的是递归算法,代入n=8,得到的值是21,D正确。 D 22 4. 有如下程序段: def f(x,n): 　　if n==0: 　　　　return 1 　　else: 　　　　return x*f(x,n－1) print(f(2,10)) 程序执行后,输出的结果是(　　) A. 1 B. 1024 C. 2048 D. 362800 【解析】 本题考查递归算法的程序实现。在自定义函数中,又出现调用自定义函数本身,根据递推的过程f(2,10)=2*f(2,9)=2*2*f(2,8)…=210*f(2,1)=210=1024,B正确。 B 23 5. 有如下Python程序: def p(x): 　　if x>3: 　　　　return p(x－1)＋p(x－2)＋p(x－3) 　　else: 　　　　return x n=int(input()) print(p(n)) 若输入n的值为6时,则输出的结果是(　　) A. 6 B. 11 C. 20 D. 31 【解析】 本题考查递归算法。当n=6时,p(6)=p(5)＋p(4)＋p(3),其中p(5)=p(4)＋p(3)＋p(2) =6＋3＋2=11,由此可以求出p(6)=11＋6＋3=20,C正确。 C 24 6. 有8级楼梯,从第0级开始往上走,每次可以走一级或者两级,下列自定义函数f,可以计算走完n级楼梯有多少种走法,那么走完这8级楼梯的走法有(　　) def f(n): 　　if n==1: 　　　　return 1 　　elif n==2: 　　　　return 2 　　else: 　　　　return f(n－1)＋f(n－2) A. 34种 B. 35种 C. 36种 D. 37种 A 25 【解析】 这是关于前2个数为1,2的斐波那契数列的应用,在程序中使用递归算法思想解决。根据递归调用的规则可以推出递推式为 f(n)=f(n－1)＋f(n－2),因此f(3)=f(1)＋f(2)=3, f(4)=f(2)＋f(3)=5, f(5) =f(4)＋f(3)=8, f(6)=f(5)＋f(4) =13, f(7)=f(6)＋ f(5)=21, f(8)=f(7)＋f(6)=34,A正确。 7. 有如下Python程序段: def trans(m,n): 　　if m!=0: 　　　　r=m%n 　　　　return trans(m//n,n)＋str(r) 　　else: 　　　　return "0" a=int(input("a=")) b=int(input("b=")) print(trans(a,b)) 执行该程序段,依次输入11和2,则输出的结果是(　　) A. 1011 B. 1101 C. 01011 D. 11010 C 27 【解析】 本题考查递归算法以及进制转换问题。列出表格如下:   trans(11,2) trans(5,2) trans(2,2) trans(1,2) trans(0,2) 返回值 trans(5,2) ＋"1" trans(2,2) ＋"11" trans(1,2) ＋"011" trans(1,2) ＋"1011" “01011” 综上,C正确。 8. 有如下Python程序段: def f(x): 　　if x==1 or x==2: 　　　　return 1 　　else: 　　　　return f(x－1)＋f(x－2) s=0 for i in range(2,6): 　　s＋=f(i) print(s) 执行该程序段后,变量s的值是(　　) A. 20 B. 19 C. 12 D. 11 【解析】 本题的递归式是f(x)=f(x－1)＋f(x－2),边界值为:当x为1或2时,返回1,即x从3开始,f(x)为前两项的和,循环中s对f(2)到f(5)进行求和,即s=1＋2＋3＋5=11,D正确。 D 29 关键能力练 30 9. 定义如下递归函数,计算正整数n的每位数字之和,例如n=123,函数返回值为6。 def f(n): 　　x = 　　(1)　　 　　if x==0: 　　　　　return n 　　else: 　　　　　y = 　　　(2)　　　 　　　　　return 　　(3) 　　 上述程序段方框处可选的代码如下: ①n%10　②n//10　③y＋f(x)　④y＋f(n － 1) 则方框处的代码依次是(　　) A. ①②③ B. ①②④ C. ②①③ D. ②①④ C 31 【解析】 本题考查递归代码的分析与理解能力。计算正整数n的每位数字之和,可以得出其递归公式:f(n)=f(n//10)＋n%10,当n<10时递归结束。结合题目给出的代码,依次分别是(1)n//10、(2)n%10、(3)y＋f(x),C正确。 10. 定义如下函数: 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(2,"A","B","C"),输出的第一行内容是(　　) A. a－>c B. A－>C C. a－>b D. A－>B D 33 【解析】 本题考查递归算法及自定义函数知识。由代码可知,此为汉诺塔的递归函数,递归结束条件是n=1。将move(2,"A","B","C")中的条件代入模拟后可以发现,第一行是move(1,"A","C","B"),此时满足递归函数的结束条件,因此执行print语句,按照参数的先后次序关系,第一行应该输出A－> B,D正确。 11. 有如下Python程序段来判断是否为素数: from math import sqrt def prime(x,y): 　　if y>int(sqrt(x))＋1: 　　　　return _______________ 　　elif x<2 or x%y==0: 　　　　return _______________ 　　else: 　　　　return _______________ a=int(input("请输入正整数:")) if prime(a,2): 　　print(a,"是素数!") else: 　　print(a,"不是素数!") 上述程序段中画线处可选的代码如下: ①True　②False　③prime(x,y＋1) 画线处应填入的代码的顺序是(　　) A. ②③① B. ②①③ C. ①③② D. ①②③ D 35 【解析】 本题考查递归算法及自定义函数知识。本题的突破点是,根据素数问题的定义,以及代码elif x<2 or x%y==0,此时x能被y整除,因此x肯定不是素数,故返回值应该是False,D正确。 12. 运行下列Python程序段,输出结果是(　　) def trans(n): 　　if n <= 1: 　　　　return str(n) 　　else: 　　　　return trans(n//2)＋ str(n%2) print(trans(13)) A. 1101 B. 1011 C. 13 D. 31 【解析】 本题考查递归算法及自定义函数知识。由代码可知,递归函数trans的递归结束条件是n<=1。若参数n>1则进入递归调用,将参数n=13条件代入函数模拟后可以发现,trans(13)=trans(6)＋"1"=trans(3)＋"01"=trans(1)＋"101",此时满足递归函数的结束条件,因此最左边的值为“1”,因此最终结果为“1101”,A正确。该递归函数的功能是将参数n转换为二进制输出。 A 37 13. 有如下Python程序段: def f(x): 　　　if x == 1 or x == 2: 　　　　　return 1 　　　else: 　　　　　return f(x － 1)＋ f(x － 2) s = 0 for i in range(1, 4): 　　　s ＋= f(i) print(s) 执行该程序段后,f函数被调用的次数是(　　) A. 3 B. 4 C. 5 D. 10 【解析】 本题考查自定义函数调用相关知识。在循环中求f(1)＋f(2)＋f(3)的和,其中f(1)调用了1次f函数,f(2)调用了1次f函数,f(3)调用了3次f函数,一共5次。C正确。 C 38 14. 有如下 Python 程序段: def fac(n): 　　if n==0 :　#① 　　　　s=1 　　else: 　　　　s=n*fac(n－1) 　　return s print(fac(3)) 下列说法中,错. 误. 的是(　　) A. 该程序运用了递归算法 B. 程序运行后,fac()函数被调用3次 C. 若问题规模为n,该程序段的时间复杂度为O(n) D. 将①处代码改为“n==1”,该程序功能不变 【解析】 本题考查自定义函数和递归。fac()函数被调用4次,B符合题意。 B 39 15. 定义如下函数: def f(k): 　　if k<=3: 　　 　print(k) 　　 　return 　　for i in range(1,4): 　　 　f(k－i) 　　return 执行语句f(6),则f(3)被调用的次数为(　　) A. 1次 B. 2次 C. 3次 D. 4次 【解析】 本题考查递归函数相关知识。f(6)执行for语句调用f(5)、f(4)、f(3);f(5)执行for语句调用f(4)、f(3)、f(2);f(4)执行for语句调用f(3)、f(2)、f(1)。可知f(6)、f(5)、f(4)分别调用f(3)一次,f(4)被调用了2次,所以f(3)一共被调用4次。D正确。 D 40 $