资源简介

专题10　迭代与递归
学习目标　
1.根据代码的运行次数与n的关系，掌握时间复杂度的计算方法；
2.掌握迭代算法的本质是每一次迭代得到的结果会作为下一次迭代的初始值；
3.掌握递归算法的本质通过重复将问题分解为同类的子问题而解决问题的方法.
一个算法中的语句执行次数称为语句频度或时间频度，算法中基本操作重复执行的次数是问题规模n的某个函数，记为T(n)。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。时间复杂度从小到大依次为常数阶、对数阶、线性阶、平方阶和指数阶。复杂问题的求解过程常常包含基本操作的多次重复进行，重复基本操作的常用方式有迭代和递归。迭代一般采用循环结构，通过某种递推式，不断更新变量新值，直到得到问题的解。递归则是算法中存在自调用，将大问题化为相同结构的小问题来求解，递归是一种有效的算法设计方法。
(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
重难点　递归算法
算法基于数据结构，而数据结构又是算法的基础，根本目的是提高算法效率。迭代和递归是两种不同的算法思想，是一种解决问题的策略。迭代算法是一种通过重复执行一系列计算步骤来逐渐逼近或求解问题的方法。递归算法将一个复杂的问题分解为更小的、相似的子问题，直到达到一个基本的、可以直接解决的边界情况。先通过递推，找到递归出口，再逐步进行回归，得到问题的解。递归算法往往有两类，一类是对递推公式的递归，一类是过程的递归。算法的时间复杂度在很大程度上能很好地反映出算法的优劣，他是关于规模为n的函数，可以理解为程序代码中语句的运行次数的最高阶。时间复杂度从小到大依次为常数阶、对数阶、线性阶、平方阶和指数阶。相对现在万亿计的数据规模，首项系数完全可以忽略，如n*n运算次数相对10000n的运算次数，当n的规模很大时，系数10000相对来说就很渺小了。时间复杂度关键就是要分析循环结构的运行情况和次数。
例1 定义如下函数：
def rf(n)：
　 if n<3：
　 return n
　 return rf(n－1)＋rf(n－3)
执行语句v＝rf(5)，函数rf被调用的次数是(　　)
A.11 B.5 C.7 D.15
变式1 定义如下函数：
def f(x，y)：
　 if y＝＝0 or x＝＝y：
　　　return 1　#①
　 else：
　　　return f(x－1，y－1)＋f(x－1，y)
执行语句k＝f(3，2)，以下说法正确的是(　　)
A.k的值为3
B.该算法的时间复杂度为O(n)
C.f(2，1)被调用了2次
D.①处代码只执行了1次
例2 定义如下函数：
def p(x，y)：
　 if x%y＝＝0：
　 print(y)
　 else：
　 p(y，x%y)
　print(y)
执行语句 p(64，18)后，依次输出的结果为(　　)
A.8，10，8，2 B.2，8，10，18
C.4，10，18 D.18，10，4
变式2 定义如下函数：
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
重难点　递归算法
1.定义如下函数：
def f(n，k)：
　 if n＝＝k or k＝＝0:
　 return 1
　 else：
　return f(n－1，k)＋f(n－1，k－1)
执行语句ans＝f(5，3)后，ans的值为(　　)
A.2 B.8 C.10 D.20
2.定义如下函数：
def f(x)：
　 if x＝＝1：
　 return 1
　 else：
　 return (f(x－ 1)＋1)*2
执行语句 k＝f(5)后，k 的值为(　　)
A.46 B.22 C.10 D.4
3.有如下Python程序：
def fun(x)：
　 if x＝＝1：
　 return″1″
　 elif x%2＝＝0：
　 return str(x)＋'－'＋fun(x∥2)
　 else:
　 return str(x)＋'－'＋fun(x*3＋1)
print(fun(5))
执行该程序后，输出的结果是(　　)
A.5－2－7－3－6－3－1
B.1－2－4－8－16－5
C.5－16－8－4－2－1
D.1－4－8－16－5
4.有如下Python程序：
def hill(n)：
　 if n＝＝1 or n＝＝2:
　 return 1
　 elif n＝＝3：
　 return 2
　 else：
　　　 return hill(n－1)＋hill(n－3)
x＝int(input())
print(hill(x))
执行该程序，若输入的值为7，输出的结果是(　　)
A.7 B.8 C.9 D.10
5.定义如下函数：
def pd(s)：
　 if len(s) <＝ 1：
　　 return True
　 elif s[0] ！＝ s[len(s) － 1]:
　　　return False
　 else：
　　　return pd(s[1：len(s)－1])
执行语句 f ＝ pd(″abcba″)，函数 pd 被调用的次数是(　　)
A.2 B.3 C.4 D.5
6.定义如下函数：
def tob(n)：
　 if n＝＝0：
return ″″
else：
return tob(n∥2)＋str(1－n%2)
执行语句s＝tob(10)后，s的值为(　　)
A.″1010″ B.″0101″ C.″1001″ D.″1100″　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
7.定义如下函数：
def f(n)：
　 if n ＝＝ 0: return 1
　 if n <＝ 2: return n
　 return climb(n － 1) ＋ climb(n － 2) ＋ climb(n － 3)
执行语句m ＝ climb(5)后，函数climb被调用的次数(　　)
A.7 B.12 C.13 D.14　　　　　　　　　　　　　　　　
8.定义如下函数：
def search(lst, i, j, key)：
　 if i > j：
　 return －1
　 m＝(i ＋ j) ∥ 2
　 if lst[m]>key：
　 return search(lst, i，m－1，key)
　 elif lst[m] < key：
　 return search(lst, m＋1，j，key)
　else：
　 return m
若列表lst为[12，31，47，50，55，55，71，76]，执行语句search(lst，0，7，51)，该函数被调用的次数为(　　)
A.1 B.2 C.3 D.4
9.有如下程序段：
from random import randint
def f(i, j)：
　 if i >＝ j：
　 return 0
　 t ＝ randint(1，2)　#randint(1，2)随机生成1或2
　 return f(i ＋ t, j) ＋ 1
执行语句k ＝ f(0，5)后，k的值不可能为(　　)
A.3 B.4 C.5 D.6
10.有如下函数：
def f(m，n)：
　 s＝″″
　 if m>1：
　　　 if m%n＝＝0：
　　　 s＝f(m∥n，n)＋str(n)
　　 else：
　　　 s＝f(m，n＋1)
return s
执行语句 k＝f(45，2)后，k的值为(　　)
A.″533″ B.″53″ C.″35″ D.″335″
重难点　递归算法
1.定义如下函数：
def myfun(a，s)：
　 if a*2>＝ s：
　　　return a
　 else：
　　　return myfun(a ＋3, s － 2)
执行语句n＝ myfun(4，18)后， n的值为(　　)
A.4 B.7 C.10 D.13
2.有如下Python程序段：
def f(x)：
　 if x＝＝1：
return 2
　 else：
return f(x－1)**2
print(f(3))
执行该程序段后，输出的结果是(　　)
A.4 B.8 C.16 D.32
3.定义如下函数：
def f(x，y)：
　 if x<＝2 or y>20：
　 return x＋y
　 return f(x－1，y＋1)
执行语句 k ＝ f(5，1)后，k的值为(　　)
A.6 B.7 C.8 D.9
4.定义如下递归函数：
def f(a, n)：
　 n＝n－1
　 if n＝＝0：
　 return a
　 else：
　 return f(a－1，n)＋f(a＋1，n)
print(f(5，3))
程序运行后﹐输出的结果是(　　)
A.10 B.20 C.30 D.40
5.定义如下函数：
def f(s，r)：
　 if s－r**2<0 or r＝＝0:
　 return r＋1
　 else：
　return f(s－r**2，r－1)
执行语句k＝f(50，5)后，k的值为(　　)
A.4 B.3 C.2 D.1
6.有如下Python程序段：
def f(s)：
　 if len(s)＝＝1：
　 return True
　 elif len(s)＝＝2：
　 return s[0]＝＝s[1]
　 elif s[0]＝＝s[－1]：
　 return f(s[1：－1])
　 else：
　 return False
print(f(″1234321″))
执行该程序段后，下列说法正确的是(　　)
A.输出结果为False
B.函数f运用了迭代算法
C.函数f的调用次数为4
D.函数f的时间夏杂度为O(n2)
7.下面Python 程序运行后，输出结果不可能的是(　　)
from random import randint
a＝[3，4，5，6，7，8]
def f(x)：
　 if x<2：
　 return a[x]＋f(2*x＋randint(1，3))
　 else：
　 return a[x]
print(f(0))
A.8 B.9 C.10 D.13
8.定义如下函数：有如下Python程序段：
def fab(a，b)：
　 if a%b＝＝0 ：
　 return b
　 elif a>b：
　 return fab(a－b，b)
　else：
　 return fab(a，b－a)
print(fab(8，4)－ fab(4，8))
程序运行后，输出的结果为(　　)
A.0 B.2 C.4 D.8
9.有如下Python自定义函数：
def fun(x, i)：
　 if x　　　return i
　 elif x%i＝＝0：
　　　return x
　 else：
　　　return fun(x－i, i＋1)
执行语句k＝fun(37，3)后，k的值为(　　)
A.5 B.6 C.30 D.34
10.有如下 Python 程序：
def trans (n)：
　 ch ＝″0123456789ABCDEF″
　 if n<16：
　 return ch[n % 16]
　 else：
　 digit＝ trans(n ∥ 16) ＋ ch[n% 16]
　 return digit
n＝ int(input(″请输入一个正整数：″))
print (trans (n))
执行该程序时，输入“268”(不含引号)，则输出的结果为(　　)
A.C01 B.C010 C.10C D.010
11.有如下自定义函数：
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.该程序采用了递归算法
12.定义如下函数：
def chg(k)：
　 if k＝＝－1：
　　　return ″″
　 else：
　　　c＝chr(ord(″a″)＋k)
　　　if k%2＝＝1：
　　　 return c＋chg(k－1)
　　　else：
　　　 return chg(k－1)＋c
执行语句m＝chg(4)后，m的值为(　　)
A.″ecabd″ B.″dbace″
C.″abcde″ D.″edcba″
专题10　迭代与递归
学习目标　
1.根据代码的运行次数与n的关系，掌握时间复杂度的计算方法；
2.掌握迭代算法的本质是每一次迭代得到的结果会作为下一次迭代的初始值；
3.掌握递归算法的本质通过重复将问题分解为同类的子问题而解决问题的方法.
一个算法中的语句执行次数称为语句频度或时间频度，算法中基本操作重复执行的次数是问题规模n的某个函数，记为T(n)。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。时间复杂度从小到大依次为常数阶、对数阶、线性阶、平方阶和指数阶。复杂问题的求解过程常常包含基本操作的多次重复进行，重复基本操作的常用方式有迭代和递归。迭代一般采用循环结构，通过某种递推式，不断更新变量新值，直到得到问题的解。递归则是算法中存在自调用，将大问题化为相同结构的小问题来求解，递归是一种有效的算法设计方法。
(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
答案　C
解析　本题考查递归函数的应用。递归算法包含递推和回归两部分，函数f(6，21)的值为 f(7，15)，而f(7，15)的值为 f(8，8)，函数f(8，8)的值为8，依次回归，最终函数的值为8。
重难点　递归算法
算法基于数据结构，而数据结构又是算法的基础，根本目的是提高算法效率。迭代和递归是两种不同的算法思想，是一种解决问题的策略。迭代算法是一种通过重复执行一系列计算步骤来逐渐逼近或求解问题的方法。递归算法将一个复杂的问题分解为更小的、相似的子问题，直到达到一个基本的、可以直接解决的边界情况。先通过递推，找到递归出口，再逐步进行回归，得到问题的解。递归算法往往有两类，一类是对递推公式的递归，一类是过程的递归。算法的时间复杂度在很大程度上能很好地反映出算法的优劣，他是关于规模为n的函数，可以理解为程序代码中语句的运行次数的最高阶。时间复杂度从小到大依次为常数阶、对数阶、线性阶、平方阶和指数阶。相对现在万亿计的数据规模，首项系数完全可以忽略，如n*n运算次数相对10000n的运算次数，当n的规模很大时，系数10000相对来说就很渺小了。时间复杂度关键就是要分析循环结构的运行情况和次数。
例1 定义如下函数：
def rf(n)：
　 if n<3：
　 return n
　 return rf(n－1)＋rf(n－3)
执行语句v＝rf(5)，函数rf被调用的次数是(　　)
A.11 B.5 C.7 D.15
思维点拨
明考向 本题考查递归算法思想
精点拨 当参数n大于等于3时，两次递归调用，否则直接返回值。①rf(5)＝rf(4)＋rf(2)，调用rf函数2次；②rf(4)＝rf(3)＋rf(1) ，调用rf函数2次；③rf(3)＝rf(2)＋rf(0)，调用rf函数2次；再加上v＝rf(5)本身调用的一次，共7次。画出递推的过程如图所示，图中显示调用函数的次数为7.
答案　C
变式1 定义如下函数：
def f(x，y)：
　 if y＝＝0 or x＝＝y：
　　　return 1　#①
　 else：
　　　return f(x－1，y－1)＋f(x－1，y)
执行语句k＝f(3，2)，以下说法正确的是(　　)
A.k的值为3
B.该算法的时间复杂度为O(n)
C.f(2，1)被调用了2次
D.①处代码只执行了1次
答案　A
解析　本题考查递归算法思想。根据函数画出递推过程如图所示。
A选项在回归过程中，f(1，0)＋f(1，1) 即f(2，1)值为2，f(2，2)值为1，因此函数的值为3。B选项从递推公式f(x－1，y－1)＋f(x－1，y)来看，形成一个二叉树，因此问题规模n是二叉树的高度，当最坏的情况下，有2n－1个节点，时间复杂度为O (2n)。C选项f(2，1)被调用了1次。D选项①处代码只执行了3次。
例2 定义如下函数：
def p(x，y)：
　 if x%y＝＝0：
　 print(y)
　 else：
　 p(y，x%y)
　print(y)
执行语句 p(64，18)后，依次输出的结果为(　　)
A.8，10，8，2 B.2，8，10，18
C.4，10，18 D.18，10，4
思维点拨
明考向 本题考查递归函数的应用
精点拨 本题考查递归函数的应用函数P(x，y)调用四次，依次是p(64，18)，p(18，10)，p(10，8)，p(8，2)。函数每调用一次输出一个y值，输出的顺序跟调用函数的顺序是逆序的，即先输出p(8，2)时的y值2，然后依次是8，10，18。画出递推公式如图所示，回归后得到答案B
答案　B
变式2 定义如下函数：
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
解析　本题考查递归函数的应用。执行语句move(2，″A″，″B″，″C″)，分别调用move(1，″A″，″C″″B″，)，move(1，″A″，″B″，″C″)，move(1，″B″，″A″，″C″)，因此分别输出A→B、A→C、B→C。画出递推公式如图所示，回归后得到答案。
重难点　递归算法
1.定义如下函数：
def f(n，k)：
　 if n＝＝k or k＝＝0:
　 return 1
　 else：
　return f(n－1，k)＋f(n－1，k－1)
执行语句ans＝f(5，3)后，ans的值为(　　)
A.2 B.8 C.10 D.20
答案　C
解析　函数f(5，3)的值为f(4，3)＋f(4，2)，函数f(4，3)的值为f(3，3)＋f(3，2)，函数f(3，3)的值1，函数f(3，2)的值为f(2，2)＋f(2，1)，函数f(2，2)的值为1，函数f(2，1)的值为f(1，1)＋f(1，0)＝2，函数f(1，1)和函数f(1，0)的值均为1。可得函数f(4，3)的值为4。函数f(4，2)的值为f(3，2)＋f(3，1)，函数f(3，2)的值为f(2，2)＋f(2，1)＝1＋2＝3。函数f(3，1)的值为f(2，1)＋f(2，0)＝3。可得函数f(4，3)的值为6，而f(4，3)＋f(4，2)的值为10。
2.定义如下函数：
def f(x)：
　 if x＝＝1：
　 return 1
　 else：
　 return (f(x－ 1)＋1)*2
执行语句 k＝f(5)后，k 的值为(　　)
A.46 B.22 C.10 D.4
答案　A
解析　函数f(5)的值为(f(4)＋1)*2，函数f(4)的值为(f(3)＋1)*2，函数f(3)的值为(f(2)＋1)*2，函数f(2)的值为(f(1)＋1)*2＝4。回归可得f(3)＝10，f(4)＝22，f(5)＝46。
3.有如下Python程序：
def fun(x)：
　 if x＝＝1：
　 return″1″
　 elif x%2＝＝0：
　 return str(x)＋'－'＋fun(x∥2)
　 else:
　 return str(x)＋'－'＋fun(x*3＋1)
print(fun(5))
执行该程序后，输出的结果是(　　)
A.5－2－7－3－6－3－1
B.1－2－4－8－16－5
C.5－16－8－4－2－1
D.1－4－8－16－5
答案　C
解析　程序的功能是将一个数n转换成1的过程，若n为偶数，n更新为x∥2，否则更新为x*3＋1，直到n的值为1。
4.有如下Python程序：
def hill(n)：
　 if n＝＝1 or n＝＝2:
　 return 1
　 elif n＝＝3：
　 return 2
　 else：
　　　 return hill(n－1)＋hill(n－3)
x＝int(input())
print(hill(x))
执行该程序，若输入的值为7，输出的结果是(　　)
A.7 B.8 C.9 D.10
答案　C
解析　函数hill(7)返回值为hill(6)＋hill(4)；函数hill(6)返回值为hill(5)＋hill(3)；函数hill(5)返回值为hill(4)＋hill(2)；函数hill(4)返回值为hill(3)＋hill(1)；因此hill(4)＝3，hill(5)＝4，hill(6)＝6，hill(7)＝9。
5.定义如下函数：
def pd(s)：
　 if len(s) <＝ 1：
　　 return True
　 elif s[0] ！＝ s[len(s) － 1]:
　　　return False
　 else：
　　　return pd(s[1：len(s)－1])
执行语句 f ＝ pd(″abcba″)，函数 pd 被调用的次数是(　　)
A.2 B.3 C.4 D.5
答案　B
解析　程序的功能是判断字符串s是否是对称字符串。pd(″abcba″)返回pd(″bcb″)，pd(″bcb″)返回pd(″c″)，pd(″c″)返回True，因此调用3次。
6.定义如下函数：
def tob(n)：
　 if n＝＝0：
return ″″
else：
return tob(n∥2)＋str(1－n%2)
执行语句s＝tob(10)后，s的值为(　　)
A.″1010″ B.″0101″ C.″1001″ D.″1100″
答案　B
解析　程序的功能将10转换成二进制并用反码表示，则″1010″的反码为″0101″。　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
7.定义如下函数：
def f(n)：
　 if n ＝＝ 0: return 1
　 if n <＝ 2: return n
　 return climb(n － 1) ＋ climb(n － 2) ＋ climb(n － 3)
执行语句m ＝ climb(5)后，函数climb被调用的次数(　　)
A.7 B.12 C.13 D.14
答案　C
解析　climb(5)＝climb(4)＋climb(3)＋climb(2)，climb(4)＝climb(3)＋climb(2)＋climb(1)，climb(3)＝climb(2)＋climb(1)＋climb(0)，根据函数画出递推过程如图所示，共调用了13次climb函数。
　　　　　　　　　　　　　　　　
8.定义如下函数：
def search(lst, i, j, key)：
　 if i > j：
　 return －1
　 m＝(i ＋ j) ∥ 2
　 if lst[m]>key：
　 return search(lst, i，m－1，key)
　 elif lst[m] < key：
　 return search(lst, m＋1，j，key)
　else：
　 return m
若列表lst为[12，31，47，50，55，55，71，76]，执行语句search(lst，0，7，51)，该函数被调用的次数为(　　)
A.1 B.2 C.3 D.4
答案　D
解析　采用递归思想编写二分查找的算法。分别调用函数search(lst，0，7，51)，search(lst，4，7，51)，search(lst，4，5，51)，search(lst，5，4，51)，最后得到结果为－1。
9.有如下程序段：
from random import randint
def f(i, j)：
　 if i >＝ j：
　 return 0
　 t ＝ randint(1，2)　#randint(1，2)随机生成1或2
　 return f(i ＋ t, j) ＋ 1
执行语句k ＝ f(0，5)后，k的值不可能为(　　)
A.3 B.4 C.5 D.6
答案　D
解析　函数的出口为i >＝ j，只要枚举每次产生t的值，当条件符合时次数就是k的值。若每次产生t的值为1，需调用函数5次，返回值为5。若产生t的值依次为1，1，1，2，则k的值为4。若产生t的值依次为1，2，2，则k的值为3。函数不可能调用6次。
10.有如下函数：
def f(m，n)：
　 s＝″″
　 if m>1：
　　　 if m%n＝＝0：
　　　 s＝f(m∥n，n)＋str(n)
　　 else：
　　　 s＝f(m，n＋1)
return s
执行语句 k＝f(45，2)后，k的值为(　　)
A.″533″ B.″53″ C.″35″ D.″335″
答案　A
解析　本题考查递归算法思想。函数f(45，2)返回值为f(45，3)；函数f(45，3)返回值为f(15，3)＋″3″；函数f(15，3)返回值为f(5，3)＋″3″；函数f(5，3)返回值为f(5，4)；函数f(5，4)返回值为f(5，5)；函数f(5，5)返回值为f(1，5)＋″5″。递推的过程如图所示，得到回归结果为″533″。
重难点　递归算法
1.定义如下函数：
def myfun(a，s)：
　 if a*2>＝ s：
　　　return a
　 else：
　　　return myfun(a ＋3, s － 2)
执行语句n＝ myfun(4，18)后， n的值为(　　)
A.4 B.7 C.10 D.13
答案　C
解析　myfun(4，18)＝ myfun(7，16)＝ myfun(10，14)，满足a*2>＝s，因此返回a。
2.有如下Python程序段：
def f(x)：
　 if x＝＝1：
return 2
　 else：
return f(x－1)**2
print(f(3))
执行该程序段后，输出的结果是(　　)
A.4 B.8 C.16 D.32
答案　 C
解析　f(3)返回值为f(2)**2，f(2)返回值为f(1)**2，f(1)返回2，因此f(2)值为4，f(3)值为4**2＝16。
3.定义如下函数：
def f(x，y)：
　 if x<＝2 or y>20：
　 return x＋y
　 return f(x－1，y＋1)
执行语句 k ＝ f(5，1)后，k的值为(　　)
A.6 B.7 C.8 D.9
答案　A
解析　f(5，1)返回值为f(4，2)，f(4，2)返回值为f(3，3) ，f(3，3)返回值为f(2，4) ，f(2，4)返回值2＋4＝6
4.定义如下递归函数：
def f(a, n)：
　 n＝n－1
　 if n＝＝0：
　 return a
　 else：
　 return f(a－1，n)＋f(a＋1，n)
print(f(5，3))
程序运行后﹐输出的结果是(　　)
A.10 B.20 C.30 D.40
答案　B
解析　f(5，3)＝f(4，2)＋f(6，2)＝ f(3，1)＋f(5，1)＋ f(5，1)＋f(7，1)＝20。
5.定义如下函数：
def f(s，r)：
　 if s－r**2<0 or r＝＝0:
　 return r＋1
　 else：
　return f(s－r**2，r－1)
执行语句k＝f(50，5)后，k的值为(　　)
A.4 B.3 C.2 D.1
答案　B
解析　分析程序段可知，函数 f(s，r)为递归函数，因此 f(50，5)＝f(25，4)＝f(9，3)＝f(0，2)＝3。
6.有如下Python程序段：
def f(s)：
　 if len(s)＝＝1：
　 return True
　 elif len(s)＝＝2：
　 return s[0]＝＝s[1]
　 elif s[0]＝＝s[－1]：
　 return f(s[1：－1])
　 else：
　 return False
print(f(″1234321″))
执行该程序段后，下列说法正确的是(　　)
A.输出结果为False
B.函数f运用了迭代算法
C.函数f的调用次数为4
D.函数f的时间夏杂度为O(n2)
答案　C
解析　考查函数递归的分析和理解。该程序段的功能是利用递归判断一个字符串是否是“回文串”。A选项″1234321″是回文串。B选项该函数内部调用了自身，是递归算法。C选项f(″1234321″)→f(″23432″)→f(″343″)→f(″4″)→True，调用4次。D选项程序内部只调用本身一次，算法复杂度是O(n)。
7.下面Python 程序运行后，输出结果不可能的是(　　)
from random import randint
a＝[3，4，5，6，7，8]
def f(x)：
　 if x<2：
　 return a[x]＋f(2*x＋randint(1，3))
　 else：
　 return a[x]
print(f(0))
A.8 B.9 C.10 D.13
答案　C
解析　若第1次产生的随机数为1，则返回a[0]＋f(2*0＋1)，即3＋ f(1)。若x的值为1，函数返回a[1]＋f(2*1＋randint(1，3))，产生随机数分别为1，2，3时，返回值依次为4＋6＝10，4＋7＝11，4＋8＝12，则3＋ f(1)的值依次为13，14，15。若第1次产生的随机数为2，则返回a[0]＋f(2*0＋2)，其值为3＋5＝8。若第1次产生的随机数为3，则返回a[0]＋f(2*0＋3)，其值为3＋6＝9。
8.定义如下函数：有如下Python程序段：
def fab(a，b)：
　 if a%b＝＝0 ：
　 return b
　 elif a>b：
　 return fab(a－b，b)
　else：
　 return fab(a，b－a)
print(fab(8，4)－ fab(4，8))
程序运行后，输出的结果为(　　)
A.0 B.2 C.4 D.8
答案　A
解析　程序的功能是辗转相除法计算两个非负整数的最大公约数。函数fab(4，8)返回fab(4，4)，函数fab(4，4)返回4。函数fab(8，4)返回4。
9.有如下Python自定义函数：
def fun(x, i)：
　 if x　　　return i
　 elif x%i＝＝0：
　　　return x
　 else：
　　　return fun(x－i, i＋1)
执行语句k＝fun(37，3)后，k的值为(　　)
A.5 B.6 C.30 D.34
答案　C
解析　 函数fun(34, 4)＝ fun(30, 5)，而30%5的值为0，因此返回30。
10.有如下 Python 程序：
def trans (n)：
　 ch ＝″0123456789ABCDEF″
　 if n<16：
　 return ch[n % 16]
　 else：
　 digit＝ trans(n ∥ 16) ＋ ch[n% 16]
　 return digit
n＝ int(input(″请输入一个正整数：″))
print (trans (n))
执行该程序时，输入“268”(不含引号)，则输出的结果为(　　)
A.C01 B.C010 C.10C D.010
答案　C
解析　本题考查递归算法、自定义函数、进制转换等相关知识。递归的方式实现十进制数转换十六进制数。268D＝10CH。
11.有如下自定义函数：
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
解析　fg(4)＝ fg(3)＋fg(2)，fg(3)＝ fg(2)＋fg(1)＝3，因此fg(4)的值为5。画出递归树如图，其中f4表示fg(4)，函数fg被调用5次，第2次调用是fg(3)。
12.定义如下函数：
def chg(k)：
　 if k＝＝－1：
　　　return ″″
　 else：
　　　c＝chr(ord(″a″)＋k)
　　　if k%2＝＝1：
　　　 return c＋chg(k－1)
　　　else：
　　　 return chg(k－1)＋c
执行语句m＝chg(4)后，m的值为(　　)
A.″ecabd″ B.″dbace″
C.″abcde″ D.″edcba″
答案　B
解析　依次调用函数时，k的值为4，3，2，1，0，因此对应的字母c依次为edcba。chg(4)＝ chg(3) ＋″e″；chg(3)＝″d″＋ chg(2) ；chg(2)＝ chg(1) ＋″c″；chg(1)＝″b″＋ chg(0) ；chg(0)＝ chg(－1) ＋″a″，依次进行回归，chg(1)＝″ba″， chg(2)＝″bac″， chg(3)＝″dbac″， chg(4)＝″dbace″。(共48张PPT)
第二部分　算法与程序设计
专题10　迭代与递归
1.根据代码的运行次数与n的关系，掌握时间复杂度的计算方法；
2.掌握迭代算法的本质是每一次迭代得到的结果会作为下一次迭代的初始值；
3.掌握递归算法的本质通过重复将问题分解为同类的子问题而解决问题的方法.
目 录
CONTENTS
体系构建
01
真题再现
02
考点精练
03
当堂检测
04
课后练习
05
体系构建
1
一个算法中的语句执行次数称为语句频度或时间频度，算法中基本操作重复执行的次数是问题规模n的某个函数，记为T(n)。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。时间复杂度从小到大依次为常数阶、对数阶、线性阶、平方阶和指数阶。复杂问题的求解过程常常包含基本操作的多次重复进行，重复基本操作的常用方式有迭代和递归。迭代一般采用循环结构，通过某种递推式，不断更新变量新值，直到得到问题的解。递归则是算法中存在自调用，将大问题化为相同结构的小问题来求解，递归是一种有效的算法设计方法。
真题再现
2
解析　本题考查递归函数的应用。递归算法包含递推和回归两部分，函数f(6，21)的值为 f(7，15)，而f(7，15)的值为 f(8，8)，函数f(8，8)的值为8，依次回归，最终函数的值为8。
C
考点精练
3
重难点　递归算法
算法基于数据结构，而数据结构又是算法的基础，根本目的是提高算法效率。迭代和递归是两种不同的算法思想，是一种解决问题的策略。迭代算法是一种通过重复执行一系列计算步骤来逐渐逼近或求解问题的方法。递归算法将一个复杂的问题分解为更小的、相似的子问题，直到达到一个基本的、可以直接解决的边界情况。先通过递推，找到递归出口，再逐步进行回归，得到问题的解。递归算法往往有两类，一类是对递推公式的递归，一类是过程的递归。算法的时间复杂度在很大程度上能很好地反映出算法的优劣，他是关于规模为n的函数，可以理解为程序代码中语句的运行次数的最高阶。时间复杂度从小到大依次为常数阶、对数阶、线性阶、平方阶和指数阶。相对现在万亿计的数据规模，首项系数完全可以忽略，如n*n运算次数相对10000n的运算次数，当n的规模很大时，系数10000相对来说就很渺小了。时间复杂度关键就是要分析循环结构的运行情况和次数。
C
思维点拨
明考向 本题考查递归算法思想
精点拨 当参数n大于等于3时，两次递归调用，否则直接返回值。①rf(5)＝rf(4)＋rf(2)，调用rf函数2次；②rf(4)＝rf(3)＋rf(1) ，调用rf函数2次；③rf(3)＝rf(2)＋rf(0)，调用rf函数2次；再加上v＝rf(5)本身调用的一次，共7次。画出递推的过程如图所示，图中显示调用函数的次数为7.
A
解析　本题考查递归算法思想。根据函数画出递推过程如图所示。
A选项在回归过程中，f(1，0)＋f(1，1) 即f(2，1)值为2，f(2，2)值为1，因此函数的值为3。B选项从递推公式f(x－1，y－1)＋f(x－1，y)来看，形成一个二叉树，因此问题规模n是二叉树的高度，当最坏的情况下，有2n－1个节点，时间复杂度为O (2n)。C选项f(2，1)被调用了1次。D选项①处代码只执行了3次。
B
思维点拨
明考向 本题考查递归函数的应用
精点拨 本题考查递归函数的应用函数P(x，y)调用四次，依次是p(64，18)，p(18，10)，p(10，8)，p(8，2)。函数每调用一次输出一个y值，输出的顺序跟调用函数的顺序是逆序的，即先输出p(8，2)时的y值2，然后依次是8，10，18。画出递推公式如图所示，回归后得到答案B
D
解析　本题考查递归函数的应用。执行语句move(2，″A″，″B″，″C″)，分别调用move(1，″A″，″C″″B″，)，move(1，″A″，″B″，″C″)，move(1，″B″，″A″，″C″)，因此分别输出A→B、A→C、B→C。画出递推公式如图所示，回归后得到答案。
当堂检测
4
重难点　递归算法
C
解析　函数f(5，3)的值为f(4，3)＋f(4，2)，函数f(4，3)的值为f(3，3)＋f(3，2)，函数f(3，3)的值1，函数f(3，2)的值为f(2，2)＋f(2，1)，函数f(2，2)的值为1，函数f(2，1)的值为f(1，1)＋f(1，0)＝2，函数f(1，1)和函数f(1，0)的值均为1。可得函数f(4，3)的值为4。函数f(4，2)的值为f(3，2)＋f(3，1)，函数f(3，2)的值为f(2，2)＋f(2，1)＝1＋2＝3。函数f(3，1)的值为f(2，1)＋f(2，0)＝3。可得函数f(4，3)的值为6，而f(4，3)＋f(4，2)的值为10。
A
解析　函数f(5)的值为(f(4)＋1)*2，函数f(4)的值为(f(3)＋1)*2，函数f(3)的值为(f(2)＋1)*2，函数f(2)的值为(f(1)＋1)*2＝4。回归可得f(3)＝10，f(4)＝22，f(5)＝46。
C
解析　程序的功能是将一个数n转换成1的过程，若n为偶数，n更新为x∥2，否则更新为x*3＋1，直到n的值为1。
C
解析　函数hill(7)返回值为hill(6)＋hill(4)；函数hill(6)返回值为hill(5)＋hill(3)；函数hill(5)返回值为hill(4)＋hill(2)；函数hill(4)返回值为hill(3)＋hill(1)；因此hill(4)＝3，hill(5)＝4，hill(6)＝6，hill(7)＝9。
B
解析　程序的功能是判断字符串s是否是对称字符串。pd(″abcba″)返回pd(″bcb″)，pd(″bcb″)返回pd(″c″)，pd(″c″)返回True，因此调用3次。
B
解析　程序的功能将10转换成二进制并用反码表示，则″1010″的反码为″0101″。　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
C
解析　climb(5)＝climb(4)＋climb(3)＋climb(2)，climb(4)＝climb(3)＋climb(2)＋climb(1)，climb(3)＝climb(2)＋climb(1)＋climb(0)，根据函数画出递推过程如图所示，共调用了13次climb函数。
解析　采用递归思想编写二分查找的算法。分别调用函数search(lst，0，7，51)，search(lst，4，7，51)，search(lst，4，5，51)，search(lst，5，4，51)，最后得到结果为－1。
D
D
解析　函数的出口为i >＝ j，只要枚举每次产生t的值，当条件符合时次数就是k的值。若每次产生t的值为1，需调用函数5次，返回值为5。若产生t的值依次为1，1，1，2，则k的值为4。若产生t的值依次为1，2，2，则k的值为3。函数不可能调用6次。
A
解析　本题考查递归算法思想。函数f(45，2)返回值为f(45，3)；函数f(45，3)返回值为f(15，3)＋″3″；函数f(15，3)返回值为f(5，3)＋″3″；函数f(5，3)返回值为f(5，4)；函数f(5，4)返回值为f(5，5)；函数f(5，5)返回值为f(1，5)＋″5″。递推的过程如图所示，得到回归结果为″533″。
课后练习
5
重难点　递归算法
C
解析　myfun(4，18)＝ myfun(7，16)＝ myfun(10，14)，满足a*2>＝s，因此返回a。
C
解析　f(3)返回值为f(2)**2，f(2)返回值为f(1)**2，f(1)返回2，因此f(2)值为4，f(3)值为4**2＝16。
A
解析　f(5，1)返回值为f(4，2)，f(4，2)返回值为f(3，3) ，f(3，3)返回值为f(2，4) ，f(2，4)返回值2＋4＝6
B
解析　f(5，3)＝f(4，2)＋f(6，2)＝ f(3，1)＋f(5，1)＋ f(5，1)＋f(7，1)＝20。
B
解析　分析程序段可知，函数 f(s，r)为递归函数，因此 f(50，5)＝f(25，4)＝f(9，3)＝f(0，2)＝3。
C
解析　考查函数递归的分析和理解。该程序段的功能是利用递归判断一个字符串是否是“回文串”。A选项″1234321″是回文串。B选项该函数内部调用了自身，是递归算法。C选项f(″1234321″)→f(″23432″)→f(″343″)→f(″4″)→True，调用4次。D选项程序内部只调用本身一次，算法复杂度是O(n)。
C
解析　若第1次产生的随机数为1，则返回a[0]＋f(2*0＋1)，即3＋ f(1)。若x的值为1，函数返回a[1]＋f(2*1＋randint(1，3))，产生随机数分别为1，2，3时，返回值依次为4＋6＝10，4＋7＝11，4＋8＝12，则3＋ f(1)的值依次为13，14，15。若第1次产生的随机数为2，则返回a[0]＋f(2*0＋2)，其值为3＋5＝8。若第1次产生的随机数为3，则返回a[0]＋f(2*0＋3)，其值为3＋6＝9。
A
解析　程序的功能是辗转相除法计算两个非负整数的最大公约数。函数fab(4，8)返回fab(4，4)，函数fab(4，4)返回4。函数fab(8，4)返回4。
C
解析　 函数fun(34, 4)＝ fun(30, 5)，而30%5的值为0，因此返回30。
C
解析　本题考查递归算法、自定义函数、进制转换等相关知识。递归的方式实现十进制数转换十六进制数。268D＝10CH。
B
解析　fg(4)＝ fg(3)＋fg(2)，fg(3)＝ fg(2)＋fg(1)＝3，因此fg(4)的值为5。画出递归树如图，其中f4表示fg(4)，函数fg被调用5次，第2次调用是fg(3)。
B
解析　依次调用函数时，k的值为4，3，2，1，0，因此对应的字母c依次为edcba。chg(4)＝ chg(3) ＋″e″；chg(3)＝″d″＋ chg(2) ；chg(2)＝ chg(1) ＋″c″；chg(1)＝″b″＋ chg(0) ；chg(0)＝ chg(－1) ＋″a″，依次进行回归，chg(1)＝″ba″， chg(2)＝″bac″， chg(3)＝″dbac″， chg(4)＝″dbace″。

展开更多......

收起↑