专题22 迭代与递归课件-2025-2026学年高考信息技术总复习

该高中信息技术高考复习课件聚焦“迭代与递归”专题，依据高考评价体系覆盖迭代概念、递归实现及典型算法（欧几里得算法、斐波那契数列）核心考点，结合核心素养中信息意识和计算思维的考查要求，通过考点诊断归纳递归函数调用、迭代变量更新等高频题型，构建备考体系。 课件亮点在于“真题驱动+算法建模+素养提升”，如以2023浙江选考递归函数题、2025台金七校联考迭代代码分析题为例，深入解析递归过程“递推-回归”及迭代变量更新技巧，培养学生计算思维和算法优化能力，特设“易错点警示”和“算法模型库”，助力学生掌握得分要点，教师可精准开展针对性复习。

专题 22 迭代与递归 1 知识梳理 归纳提升 题型考法 考点1 迭代 1.迭代的概念 （1）迭代是重复反馈过程的活动，其目的通常是为了使结果符合目标需 求。 （2）迭代利用计算机运算速度快、适合做重复性操作的特点，让计算机 ____________一组指令（或一些步骤），这组指令（或这些步骤）每执行一次时，都会将变量从原值递推出一个________。 重复执行 新值 知识梳理 归纳提升 题型考法 2.迭代的过程图示 知识梳理 归纳提升 题型考法 3.迭代的实现 （1）确定_____________：一个直接或间接地不断由旧值递推出新值的变量。 （2）建立迭代关系式：将变量从前一个值推出其下一个值的公式（或 关系）。 （3）控制迭代过程：设定迭代结束的条件。 迭代变量 知识梳理 归纳提升 题型考法 考点2 递归 1.递归的概念 递归是通过函数自己调用自己来实现的，即一个函数在其定义中有直接或间接调用自身的一种方法。 2.递归算法的实现 （1）求解问题特征：为求解规模为 N 的问题，设法将它分解成规模较 小的问题，然后从这些小问题的解中方便地构造出大问题的解， 并且这些规模较小的问题也能采用同样的分解和综合方法。 （2）当递归达到某个边界，如问题规模缩减为 0 或1 时，能直接得解。 （3）设计递归算法的关键步骤：①确定递归公式；②确定递归_______________。 结束条件 知识梳理 归纳提升 题型考法 3.递归的过程 （1）设一个递归过程中，递归公式为 f(n)=n*f(n-1)，递归结束条件为 f(1)=1，则求 f(5)的值的递归过程如图所示。 （2）f(5)可以根据递归公式 f(n)=n*f(n-1)进行逐次分解，该过程即是 “递推”，递归结束条件为f(1)=1，此时可以进行“回归”，得到 f(5) 的解。 知识梳理 归纳提升 题型考法 4.递归与栈 （1）递归对问题的处理顺序，遵循了_____________（先开始的问题最后结束）的规律，这天然地符合栈这种数据结构的特性。递归和栈之 间有一种紧密的联系。我们可以把任意一个递归程序转换成一个 使用栈的程序。 （2）设一个递归过程中，递归公式为 f(n)=n*f(n-1)，递归结束条件为 f(1)=1，利用栈的思想求 f(6)的值的递归过程如下图所示。 先入后出 知识梳理 归纳提升 题型考法 ①递推与入栈：递归公式为 f(n)=n*f(n-1)，则每一步使 f(n-1)逐个入栈， 从而实现“递推”。 ②回归与出栈：将获得的递归结束条件中 f(1)的值出栈，实现“回归”， 在回归的过程中每一步都会返回一个值，直到得到待求解问题 f(6)的 值则终止。 知识梳理 归纳提升 题型考法 5.递归与二叉树 （1）二叉树是递归算法典型的例子，与二叉树有关的问题，可以利用 递归思想来解决。 （2）递归与二叉树的遍历（以前序遍历为例）。 ①递归公式（或方法）为：先遍历根节点，再遍历左子树，最后 遍历右子树。 ②递归结束条件为：某个“根节点”左、右子树为空，开始回归。 知识梳理 归纳提升 题型考法 判断正误，正确的画“√”，错误的画“×”。 1.迭代算法的效率一定高于递归算法。 （　　） 2. 递归函数不断重复调用自身，通常每次调用在规模上都有所缩小。 （　　） 3. 迭代变量在每次迭代中必须通过固定公式更新，不能依赖其他变量的动态值。 （　　） 4. 斐波那契数列的递归实现中，计算 fib(5)需要调用 fib 函数共 8 次。 （　　） 5. 递归函数 f(a,n)中若调用 f(a-1,n)+f(a+1,n)，则调用次数呈指数级增长。 （　　） × √ × × √ 知识梳理 归纳提升 题型考法 （1）整数 m、n 的最大公约数等于 n 和 m 除以 n 的余数的最大公约数。 （2）代码实现。 def gcd(m,n): while n!=0: temp=n n=m%n m=temp return m （3）m、n 是迭代变量，迭代关系是 n→m 和 m%n→n，由旧值推出新值，然后循 环执行，直到余数为 0，结束迭代。 知识梳理 题型考法 归纳提升 （1）典型示例 1——斐波那契数列。 ①斐波那契数列是指从第 3 项开始，每一项的值为前 2 项之和，该数列为 1， 1，2，3，5，8，…，n。 ②代码实现。 def fib(x): if x<=2: return 1 else: return fib(x-1)+fib(x-2) ③递归公式是 fib(x)=fib(x-1)+fib(x-2)，递归结束条件是 f(1)=1，f(2)=1。 知识梳理 题型考法 归纳提升 ④若求解函数 fib(4)的值，则需要返回 fib(3)+fib(2)，继续递推求解 fib(3) 和 fib(2)。已知 fib(3)的值为 fib(2)+fib(1)，调用 fib(2)和 fib(1)时，到达 递归出口，均返回 1。此时“递推”过程结束，进入“回归”过程，得到 fib(3)=fib(2)+fib(1)=1+1=2；继续“回归”，得到 fib(4)=fib(3)+fib(2)=2+1= 3。该过程即为一个完整的递归过程。 知识梳理 题型考法 归纳提升 （2）典型示例 2——汉诺塔游戏。 ①从左到右有 A、B、C 三根柱子，其中 A 柱子上面放着从大到小的 n 个圆盘， 现要求按照一定规则（每次只能移动一个圆盘，并且大盘子不能压在小盘子 上面），将 A柱子上的圆盘移动到 C柱子上。 知识梳理 题型考法 归纳提升 ②代码实现。 知识梳理 题型考法 归纳提升 考向 一 迭代算法及代码实现 例 1 下列关于迭代和递归的说法，正确的是（　　） A.迭代和递归在 Python中都必须用循环结构实现 B.迭代和递归是不同的算法，不能解决同一个问题 C.递归算法必须通过直接或间接调用自身来实现 D.迭代可以没有迭代结束条件，对结果一直优化 C 例 1 C 递归可以通过建立自定义函数，并在函数内调用自身实现，可以使用分支结构，不一定使用循环结构。对于同一个问题，可以使用不同的算法来解决，迭代和递归虽然是不同的算法，但是大部分时候能够解决同一个问题。迭代过程中必须要有迭代结束条件，否则程序会陷入死循环。 √ 知识梳理 归纳提升 题型考法 例 2 下列关于迭代算法和递归算法的说法，不正确的是 （　　） A.在使用递归算法时，必须有一个明确的递归结束条件，称为递归出口 B.一般来说，迭代算法效率较低，而递归算法效率较高 C.递归中一定有迭代，但迭代中不一定有递归 D.通常情况下，迭代算法和递归算法可以相互转换 B 例 2 B　递归算法和迭代算法的算法效率要根据具体算法和代码分析。 √ 知识梳理 归纳提升 题型考法 例 3 有如下 Python 程序段： n=int(input("n=")) s=1 for i in range(1,n,3): s+=i print(s) 执行该程序段后，若输入 n 的值为 20，则输出 s 的值是 （　　） A.51 B.70 C.71 D.93 C 例 3 C　该程序段的功能是求 s=1+1+4+7+10+13+16+19的和，故最后输出的结果是 71。 √ 知识梳理 归纳提升 题型考法 例 4 有如下 Python 程序段： def fac(n): res=0 for i in range(n): res+=2**i return res 执行语句 print(fac(5))后，输出的结果是 （　　） A.30 B.31 C.62 D.63 B 例 4 B fac(5) =2**0+2**1+2**2+2**3+2**4=1+2+4+8+16=31。 √ 知识梳理 归纳提升 题型考法 例 5 ［2025台金七校联考］有如下 Python程序段： a=[56,174,81,9,213,13] b=[0,0,0,0,0,0] for i in range(len(a)): for j in range(len(a)): if a[i]>a[j]: b[i]+=1 print(b) 执行该程序段后，输出的结果是 （　　） A.[2,4,3,0,5,1] B.[2,4,1,0,3,5] C.[3,1,4,5,2,0] D.[3,1,2,5,0,4] A 例 5 A　该程序段使用了两个嵌套的 for 循环来遍历数组a 的所有元素对（a[i]和 a[j]）。对于每一对元素，若 a[i]大于 a[j]，则计数器 b[i]的值增加 1，即 b[i]为 a[i]大于数组 a中其他元素的个数。 √ 知识梳理 归纳提升 题型考法 考向 二 递归算法及代码实现 例 6 ［2023浙江选考］定义如下函数： 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 C 例 6 C　根据给定的递归函数 f(a,s)，若 a 大于等于 s，则返回 a，否则递归调用 f(a+1,s-a)。首先，执行 f(6,21)，a=6，s=21，因为 a 小于 s，所以执行 else 语句，调用 f(6+1,21-6)=f(7,15)。接下来，执行 f(7,15)，a=7，s=15，因为 a 小于 s，所 以 执 行 else 语 句 ，调 用 f(7+1,15-7)=f(8,8)，继 续 执 行f(8,8)，a=8，s=8，因为 a 等于 s，所以返回 a，即 8。 √ 知识梳理 归纳提升 题型考法 例 7 ［2025浙江选考］对于任意非空字符串 s，甲、乙程序段输出结果相同，则乙程序段加框处的正确代码为 （　　） def f(s,t): if t>=len(s)-2: return s[t] return f(s,t+2)+s[t] 甲程序段 A.r=s[n-i]+r B.r=r+s[n-i-1] C.r=r+s[i] D.r=s[i]+r D 例7 D 甲程序段是一个递归函数，若 t>=len(s)-2，则返回字符 s[t]，否则递归调用 f(s,t+2)，并将结果与 s[t]拼接，因此函数 f(s,0)的作用是从字符 s[0]开始，每隔一个字符取一个字符（偶数索引），并将这些字符逆序拼接成结果字符串。乙程序段则是采用循环递推的方式，从索引 0 开始遍历字符串，步长为 2（跳过一个字符），再逆序拼接成结果字符串，故填入代码为 r=s[i]+r。 √ r="" n=len(s) for i in range(0,n,2): 　　　　　　　 print(r) 乙程序段 知识梳理 归纳提升 题型考法 例 8 ［2025湖丽衢模拟］定义如下函数： def f(x,y,flag): if flag==False: return x*y//f(x,y,not flag) if x==y: return x elif x<y: return f(x,y-x,flag) else: return f(x-y,y,flag) 执行语句 w=f(6,9,False)后，w 的值为 （　　） A.18 B.9 C.6 D.3 A 例 8 A w=f(6,9,False)=54//f(6,9,True)=54//f(6,3,True)=54//f(3,3,True)=54//3=18。 √ 知识梳理 归纳提升 题型考法 例 9 定义如下函数： def fg(n): if n<=2: return n else: return fg(n-1)+fg(n-2) 执行语句 s=fg(4)后，下列说法不正确的是（　　） A.s 的值为 5 B.函数 fg 被调用的次数是 4 C.第二次被调用的函数是 fg(3) D.该程序采用了递归算法 B 例 9 B s=fg(4)=fg(3)+fg(2)=fg(2)+fg(1)+2=2+1+2=5，函数 fg 被调用的次数是 5。 √ 知识梳理 归纳提升 题型考法 例 10 ［2025 浙江名校协作体］有如下 Python程序段： def fact1(n): s=0 while n!=0: s+=n%2 n=n//2 return s def fact2(n): if n==1: return 1 else: return 对于任意正整数 n（n≥2），两个函数的返回值相等，则方框处应填入的正确代码是 （　　） A.n%2+fact2(n//2) B.str(n%2)+fact2(n//2) C.fact2(n%2)+str(n//2) D.n//2+fact2(n%2) A 例 10 A 函数 fact1 的功能是统计 n 的二进制表示中“1”的个数。已知对于任意正整数 n（n≥2），两个函数的返回值相等，则函数fact2与函数fact1的功能相同，区别是函数 fact1 是通过迭代的方式计算，函数 fact2是通过递归的方式计算。n 为十进制数，若 m 为 n 转换成二进制数的结果，则n%2表示m的最后一位，n//2等于 m 去掉最后一位再转换为十进制数的结果（例如，10D=1010B，10//2=5，5D=101B），因此，统计 n 的二进制表示中“1”的个数，可以转换成统计n%2与n//2的二进制表示中“1”的个数之和，即 fact2(n)=n%2+fact2(n//2) （n≥2）。 √ 知识梳理 归纳提升 题型考法 例 11 定义如下函数： def f(a,n): n=n-1 if n==0: return a else: return f(a-1,n)+f(a+1,n) 执行语句 f(5,3)，函数 f被调用的次数是 （　　） A.5 B.6 C.7 D.8 C 例 11 C f(5,3)=f(4,2)+f(6,2)=f(3,1)+f(5,1)+f(5,1)+f(7,1)=3+5+5+7=20，故函数 f被调用的次数是 7。 √ 知识梳理 归纳提升 题型考法 例 12 ［2025 浙江天域联考］有如下 Python 程序段： def f(s): if len(s)==0: return 0 elif s[0]==s[-1]: return 1+f(s[1:-1]) else: return f(s[1:-1]) s="AABAA" print(f(s)) 执行该程序段后，下列说法正确的是 （　　） A.输出的结果是 3 B.最后一次调用 f时，s 的值是"B" C.函数 f被调用了 3 次 D.若将 s的值改为"AABBAA"，则输出的结果是 4 A 例 12 A f(s)=f("AABAA")=1+f("ABA")=2+f("B")=3+f("") =3，故最后一次调用 f 时 s 的值是""。函数 f 被调用了 4次 。 若将 s 的值改为 "AABBAA"，则输出的结果是 3。 √ 知识梳理 归纳提升 题型考法 例 13 ［2025绍兴模拟］有如下 Python 程序段： def fun(x,n): if x==n: return 1 if n%x==0: return fun(x,n//x)+1 else: return fun(x+1,n) print(fun(2,100)) 执行该程序段后，输出的结果是 （　　） A.2 B.3 C.4 D.5 C 例 13 C fun(2,100)=fun(2,50)+1=fun(2,25)+2=fun(3,25)+2=fun(4,25)+2=fun(5,25)+2=fun(5,5)+3=1+3=4。 √ 知识梳理 归纳提升 题型考法 例 14 ［2025杭州模拟］定义如下函数： def f(m,n): if m<=n: return m else: return f(m-1,n+2)+1 执行语句 k=f(12,5)后，k 的值为 （　　） A.9 B.10 C.11 D.12 D 例 14 D k=f(12,5)=f(11,7)+1=f(10,9)+1+1=f(9,11)+1+1+1=9+3=12。 √ 知识梳理 归纳提升 题型考法 THANK YOU $$