资源简介

(共63张PPT)
课时2　迭代与递归
第五章　数据结构与算法
1.通过实例分析，理解迭代和递归算法的基本思想，掌握利用迭代和递归算法解决问题的基本方法。2.能正确分析递归公式和递归结束条件，灵活使用迭代和递归算法解决实际问题，提升学生的计算思维。
目 录
CONTENTS
知识梳理
01
例题精析
02
随堂检测
03
巩固与提升
04
知识梳理
1
1.迭代算法的概念
不断用变量的______递推出______的过程称为迭代算法。
2.利用迭代算法解决问题，需要考虑的三个方面
(1)确定____________。
(2)建立_______________。
(3)控制____________。
迭代算法的难点在于寻找和建立正确的迭代公式，一般使用循环结构语句实现。
旧值
新值
迭代变量
迭代关系式
迭代过程
3.递归算法的概念
一个函数在其定义中___________________________来解决问题的方法称为递归算法。
递归算法的实质是：将规模大的问题分解成规模小的问题，然后从这些小问题的解中构造出大问题的解，并且这些规模较小的问题也能采用______的分解和综合方法。当递归到达某个______，如问题规模缩减为0或1时，能直接得解。
直接或间接调用自身
同样
边界
4.设计递归算法时，需要满足的两个条件
(1)确定____________。
(2)确定递归的____________(或称为边界条件)。
5.递归过程的两个阶段
(1)______：把较复杂的问题的求解递推到一些简单问题的求解。
(2)______：当获得最简单问题的解后，逐级返回依次得到稍复杂问题的解。
递归公式
结束条件
递推
回归
正确区分迭代算法和递归算法
(1)迭代是利用变量的旧值推算出变量的一个新值；而递归算法是指一个函数在其定义中直接或间接调用自身的一种方法，它通常把一个复杂的问题转化为一个与原问题相似的规模较小的问题来解决，可以极大地减少代码量，降低编程的难度。因此，迭代算法效率较高，而递归算法比较占用空间，程序运行效率较低。
(2)递归是自己调用自己，而迭代就是不断地调用赋值语句；递归中一定有迭代，但是迭代中不一定有递归，大部分情况下递归和迭代可以相互转换。
例题精析
2
例1 让计算机重复执行一组指令(或一些步骤)，这组指令(或这些步骤)每执行一次时，都会将变量从原值递推出一个新值的算法是(　　)
A.递推算法 B.递归算法 C.迭代算法 D.查找算法
C
解析　本题主要考查的是迭代算法的定义。本题中描述的算法是迭代算法，因此，答案为C。
变式训练　利用迭代算法处理问题时，其中从变量的前一个值推出其下一个值的公式的过程称为(　　)
解析　本题主要考查的是迭代算法的基本步骤。使用迭代算法的三个步骤为：确定迭代变量、建立迭代关系式、控制迭代过程，其中从变量的前一个值推出其下一个值的公式的过程称为建立迭代关系式。因此，答案为D。
D
A.确定迭代变量 B.设定迭代结束条件
C.控制迭代过程 D.建立迭代关系式
例2 丑数是指不能被2、3、5以外的质数整除的数。判断丑数的自定义函数程序如下：
B
若调用执行自定义函数ugly(30)，下列说法正确的是(　　)
A.函数返回值为False B.方框处程序应用了迭代算法
C.该程序的时间复杂度为O(n2) D.条件语句n%i＝＝0执行了3次
解析　本题考查算法思想应用。题目中对丑数的描述等价于：丑数是指只能被2、3、5整除的数。A选项30＝2*3*5，30是丑数。B选项方框中程序为当n能被i整除时，不断求n除以i的商，是一个重复反馈的过程。C选项整个除的次数不会大于n，因此时间复杂度为O(n)。D选项除2、3、5过程中，一次能除通，一次条件不成立，条件语句n%i＝＝0执行了6次。
变式训练　小明设计了一个算法求2n的值，算法思想是：先把2n转换为2*2n－1，而2n－1又可以转换为2*2n－1－1，如此继续，直到2*20，已知20＝1，再反过来，又依次求出21，22，…，直到求出了2n的值。小明求2n的值所采用的算法是(　　)
A.迭代算法 B.枚举算法 C.递归算法 D.解析算法
解析　本题主要考查的是递归算法的思想。本题中求2n的值，采用“大事化小，小事化了”的方法，符合递归算法的基本思想，因此答案为C。
C
若在自定义函数中又出现调用自定义函数本身，则程序使用的是递归算法。而迭代算法是指迭代变量通过迭代关系，由旧值不断推出新值，从而求出问题的解。
例3 定义如下函数：
A.11 B.5 C.7 D.15
C
def rf(n)：
if n<3：
return n
return rf(n－1)＋rf(n－3)
执行语句v＝rf(5)，函数rf被调用的次数是(　　)
解析　本题考查递归算法思想。当参数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次。
变式训练　下列Python程序的功能是使用递归算法求ans的值。
C
def fx(n)：
if n＝＝0：
return　1
else：
return n*fx(n－1)
x＝int(input(″please input x：″))
ans＝fx(x)
print(ans)
程序执行时，输入x的值为5，则输出的结果为(　　)
A.24 B.32 C.120 D.720
解析　本题主要考查的是递归算法的程序实现。递归函数的功能是求n的阶乘(x！＝1*2*3*…*n)，因为输入的x的值为5，因此本程序是求5的阶乘，最后输出的结果为120，答案为C。
例4 将十进制正整数转化为二进制数，对应的 Python 程序如下：
def toStr(n，base)：
　 s＝″01″
　 if n　return s[n]
　 else：
return ①________________
n＝int(input('请输入正整数：'))
result＝toStr(n，2)
print(result)
则代码中①处的语句可为(　　)
A.toStr(n∥base，base)＋s[n % base] B.s[n % base]＋toStr(n∥base，base)
C.toStr(n % base，base)＋s[n∥base] D.s[n∥base]＋toStr(n % base，base)
解析　利用递归的思想来处理十进制与其他数制的转换问题，函数功能是将每一次得到的余数作为结果逆序保存，整数部分再次利用函数进行转化，直到最后得到的整数部分小于要转换的进制数为止，转化过程结束。读程序可知，当 nA
变式训练　有如下Python程序：
def fx(x)：
if x>2：
return fx(x－1)*fx(x－2)
elif x＝＝1：
return 1
elif x＝＝2：
return 2
y＝int(input(″请输入y的值：″))
print(fx(y))
(1)该程序执行时，输入y的值为6时，输出的结果为__________；
(2)该程序执行时，输入y的值为8时，输出的结果为__________。
答案　(1)32　(2)8192
解析　本题主要考查的是递归算法。(1)当y＝5时，fx(6)＝fx(5)*fx(4)，fx(5)＝fx(4)*fx(3)，fx(4)＝fx(3)*fx(2)，fx(3)＝fx(2)*fx(1)，而fx(2)＝1，fx(1)＝1，因此，可求得fx(6)＝32；(2)当y＝8时，fx(8)＝fx(7)*fx(6)，fx(7)＝fx(6)*fx(5)，因此可求得fx(8)＝8192。
随堂检测
3
A.在使用递归算法时，必须有一个明确的递归结束条件，称为递归出口
B.一般来说，迭代算法效率较低，而递归算法效率较高
C.递归中一定有迭代，但迭代中不一定有递归
D.通常情况下，迭代算法和递归算法可以相互转换
B
解析　本题主要考查的是迭代算法和递归算法的特征。一般来说，迭代算法效率较高，而递归算法比较占用空间，程序运行效率较低，因此，答案为B。
2.在计算机内实现递归算法时所需的数据结构是(　　)
B
解析　栈的特点是先进后出，符合递归算法的思想，即在计算机内实现递归算法时使用栈数据结构，因此答案为B。
A.数组 B.栈 C.队列 D.链表
3.有如下Python程序段：
def f(x)：
　 if x＝＝1：
　return ″B″
　 else：
　 return str(1－(x%2))＋f(x－1)
L＝″″；i＝0
while i<10 ：
B
　 if i%2＝＝0 and i%3＝＝1：
　L＝L＋f(i)
i＝i＋1
print(L)
执行该程序段后，变量L的值是(　　)
A.010B B.101B C.B1101 D.B0010
4.有如下Python自定义函数：
C
解析　函数fun(34，4)＝fun(30，5)，而30%5的值为0，因此返回30。
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
5.定义如下函数：
B
解析　程序的功能是判断字符串s是否是对称字符串。pd(″abcba″)返回pd(″bcb″)，pd(″bcb″)返回pd(″c″)，pd(″c″)返回True，因此调用3次。
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.定义如下函数：有如下Python程序段：
A
解析　程序的功能是辗转相除法计算两个非负整数的最大公约数。函数fab(4，8)返回fab(4，4)，函数fab(4，4)返回4。函数fab(8，4)返回4。
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
7.输入两个正整数，使用递归算法求这两个正整数的最大公约数。
具体算法为：给定两个整数，如果两个整数相等，则最大公约数是其本身；如果不相等，取两个整数的差和两个整数中较小的数比较，相等则为最大公约数，不相等则继续上面的算法，直到相等。
实现上述功能的Python程序如下，请回答下列问题。
def gcd(x，y)：
if ①________________：
return x
else：
small＝min(x，y)
②________________
a＝int(input(″输入第一个整数：″))
b＝int(input(″输入第二个整数：″))
print(gcd(a，b))
(1)请在程序划线处填入合适的代码。
(2)程序运行时，输入两个整数分别为24、56，则输出的结果为______________。
(3)若要输出两个整数的最小公倍数，则应在程序的最后增加的语句为____________。
答案　(1)①x＝＝y　②return gcd(small，abs(x－y)) 或 return gcd(small，abs(y－x))
(2)8　(3)print(a*b∥gcd(a，b))
解析　本题主要考查的是递归算法的程序实现。(1)当两个整数相等时，最大公约数是其本身，因此①处的条件是x＝＝y；②处是递归调用，如果两个整数不相等，则取两个整数的差和两个整数中较小的数，重新求解这两个整数的最大公约数，因此②处代码为return gcd(small，abs(x－y))或return gcd(small，abs(y－x))。(2)整数24和56的最大公约数为8。(3)最小公倍数为a*b∥gcd(a，b)，因此，在程序的最后增加的语句为print(a*b∥gcd(a，b))。
4
巩固与提升
基础巩固
能力提升
1.下列Python程序的功能是：求s＝1＋2＋3＋…＋1000的和。
B
解析　本题主要考查的是迭代算法的思想。本题使用变量s记录总和，通过更改变量i的值来更新s的值，从而求出1＋2＋…＋1000的和，因此使用的算法是迭代算法，答案为B。
n＝1000
s＝0
for i in range(1，1001)：
s＝s＋i
print(″1＋2＋3＋…＋1000＝″，s)
在求s的过程中使用到的算法是(　　)
A.递归算法 B.迭代算法 C.枚举算法 D.解析算法
2.把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，最终求出原问题的解，这种算法称为(　　)
A.递归算法 B.迭代算法 C.枚举算法 D.解析算法
A
解析　本题主要考查的是递归算法思想。题目中描述的方法是递归算法，因此，答案为A。
3.某Python 程序如下：
def output(s，n)：
if n＝＝0：
　 return
print(s[n－1]，end＝″″)
output(s，n－1)
s＝input(″input a string：″)
x＝len(s)
output(s，x)
C
运行该代码，输入″12345″，则下列说法正确的是(　　)
A.输出结果为12345 B.有 0 个输出
C.n为0是递归结束条件 D.程序无法结束
解析　本题考查递归函数。 A选项递归函数借助栈这种数据结构，12345依次入栈，因此输出54321。当n为0时，return表示返回，意味着结束程序。
4.小明学习了算法后，写了以下两段代码来求斐波那契数列的第6项：
a＝1；b＝1 for i in range(2，6)： 　 c＝a＋b 　 a＝b 　 b＝c print(c) def f(n)：
　 if n＝＝1 or n＝＝2：
　return 1
　 else：
　returnf(n－1)＋f(n－2)
print(f(6))

算法一 算法二
C
下列说法正确的是(　　)
A.两种算法的时间复杂度均为O(1)
B.算法一是迭代算法，算法二是递归算法，相比之下，算法二的时间效率更高
C.执行算法二代码，f(4)共被调用了2次
D.执行算法一代码，当i＝4这一遍循环刚结束时，a的值等于5
解析　算法一为迭代算法，时间复杂度为O(n)，算法二为递归算法，f(n－1)＋f(n－2)语句每次调用2次，递归算法时间复杂度为(二叉树的节点个数)即O(2n)。D选项a的值为3。
5.编写一个简短的递归Python函数，它接受一个字符串s并输出其逆置字符串。例如字符串“dog”的逆置字符串为“god”。程序如下：
s＝input(″请输入字符串：″)
def reverse(s)：
if len(s)<＝1：
return s
return ①________
print(″逆置字符串为：″，reverse(s))
C
①处的代码应为(　　)
A.s[－1]＋reverse(s[1：]) B.reverse(s[1：])＋s[－1]
C.s[－1]＋reverse(s[：－1]) D.reverse(s[：－1])＋s[－1]
解析　本题主要考查的是递归算法。将一个字符串分解成两部分，即最后一个字符和前面的所有字符，逆置时只要把最后一个字符放到最前面，前一部分的子串使用同样的逆置方法即可。当规模n＝1时，直接得解，即逆置字符串为其自身。s的最后一个字符表示为s[－1]，前面的子串表示为s[：－1]，因此答案为C。
6.有如下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))
C
执行该程序后，输出的结果是(　　)
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
解析　程序的功能是将一个数n转换成1的过程，若n为偶数，n更新为x∥2，否则更新为x*3＋1，直到n的值为1。
7.有如下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))
C
执行该程序，若输入的值为7，输出的结果是(　　)
A.7 B.8 C.9 D.10
解析　函数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(6)＝9。
8.有如下函数：
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
A
执行语句 k＝f(45，2)后，k 的值为(　　)
A.″533″ B.″53″ C.″35″ D.″335″
解析　本题考查递归算法思想。函数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″。
9.对于任意一个自然数，若该自然数为偶数，则将其除以2；若是奇数，则将其乘以3，然后再加 1。如此经过有限次运算后，总能够得到自然数1 。
编写一个程序，由键盘输入一个自然数x，把n经过有限次运算后，输出最终变成1的全过程，并计算运算的次数。
程序运行结果如图所示：
请输入一个整数：24
21→12→6→3→10→5→16→8→4→2→1
运算次数为：10
实现上述功能的Python程序如下，请回答下列问题。
x＝int(input(″请输入一个整数：″))
print(x，″→″，end＝″″)
n＝0
while　x！＝1：
if ①________________：
　　　　x＝x*3＋1
(1)请在程序划线处填入合适的代码。
(2)程序执行时，输入x的值为120，则运算次数为__________。
答案　(1)①x % 2＝＝1 或x % 2！＝0
②x＝x∥2　③n＋＝1 或 n＝n＋1　(2)20
解析　本题主要考查的是迭代算法的程序实现。(1)本题使用的是迭代算法，当自然数变为1时，循环结束，否则，若x为奇数时，x＝n*3＋1，因此，①处代码为x % 2＝＝1或x % 2！＝0；若x为偶数时，x＝x∥2，因此②处语为x＝x∥2；每循环一次表示一次运算，根据语句print(″运算次数为：″，n)可知，变量n的功能是统计运算次数，因此③处代码为n＋＝1或n＝n＋1。
(2)程序执行时，输入n的值为120时，变量x的值的变化过程为：120 →60→30→15→46→23→70→35→106→53→160→80→40→20→10→5→16→8→4→2→1，因此共运算20次。
10.有如下 Python 程序段：
def f(n)：
　 if n<2：
　return 0
elif n % 2＝＝0：
　return n＋f(n－2)
else：
　return f(n－1)
n＝int(input())
print(f(n))
C
若输入 n 的值为 101，则程序运行后，输出的内容为(　　)
A.100 B.2500 C.2550 D.5050
解析　本题考查递归算法的应用。f(100)＝100＋f(98)，f(98)＝98＋f(96)，而后面的参数均为偶数，依此类推，可得：f(100)＝100＋98＋96＋94＋…＋2＝2550。
11.李华同学尝试使用递归算法来实现斐波那契数列求值，用 Python 程序实现如下。
def fibo(n)：
　 if n＝＝0 or n＝＝1：
　s＝n
else：
　 s＝fibo(n－1)＋fibo(n－2)
return s
n＝int(input(″输入所求项：″))
print(fibo(n))
有关递归算法及其应用，下列说法正确的是(　　)
A.递归算法的执行过程分递推和回归两个阶段
B.计算机在执行递归程序时，通过队列的调用来实现
C.使用上述递归算法求斐波那契数列，时间复杂度为O(n)
D.求斐波那契数列的第6项fibo(5)时，fibo(3)被调用了3次
A
解析　本题考查递归算法。A选项递归函数中包含一个递推公式，先依次调用自己，再进行回归。B选项通过栈调用来实现。C选项以第6项fibo(5)为例，可以画出二叉树来表示，
若根节点为n，则树的高度为n，深度为n的满二叉树的节点数量(函数的调用次数)为n2－1，因此时间复杂度为O(n2)。D选项fibo(3)被调用了 2次。
fibo(5)＝fibo(4)＋fibo(3)；
fibo(4)＝fibo(3)＋fibo(2)。
12.斐波那契数列指的是这样一个数列：1，1，2，3，5，8，13，21，34，55，……。这个数列的规律是：从第3项开始，每一项都等于前两项之和。
求数列中第n项(n≥3)的数据的程序如下，请回答下列问题：
def fibo(x)：
if x＝＝1：
return 1
elif x＝＝2：
return 1
else：
return ①________
n＝int(input(″n＝″))
print(″第″，n，″项为″，②________)
(1)该程序中函数fibo()采用了________思想。
(2)阅读程序，补充划线处的代码。
答案　(1)递归算法　(2)①fibo(x－1)＋fibo(x－2)　②fibo(n)
解析　本题主要考查的是递归算法的实现过程。根据题意分析递归公式为：当x<＝2时，fibo(x)＝1；当x>2时，fibo(x)＝fibo(x－1)＋fibo(x－2)，所以空①处答案为fibo(x－1)＋fibo(x－2)；空②处调用递归函数fibo()计算数列的第n项，故答案是fibo(n)。
13.求从自然数1、2、……、n中任取r个数的所有组合。例如n＝5，r＝3的所有组合为：
(1)5、4、3
(2)5、4、2
(3)5、4、1
(4)5、3、2
…
(10)3、2、1
实现上述功能的Python代码如下，请在程序划线处填入合适的代码：
def comb(m，k)：
global c　　#定义c为全局变量
for i in range(m，k－1，－1)：
①________________
if k>1：
　　　②________________
else：
　　c＋＝1
　　print(″(″＋str(c)＋″)″，end＝″″)
　　for j in range(lista[0]，0，－1)：
　　print(lista[j]，end＝″″)
　　print()
lista＝[0]*100
n＝int(input(″请输入n：″))
r＝int(input(″请输入r：″))
lista[0]＝r
c＝0
③________________
程序划线①处应填入的语句为：______________________________________；
程序划线②处应填入的语句为：________________________________________；
程序划线③处应填入的语句为：_________________________________________。
答案　①lista[k]＝i　②comb(i－1，k－1) ③comb(n，r)
解析　列表lista存放求出的组合的数字，本题中将确定的k个数字组合的第一个数字放在lista[k]中，变量c用来统计组合数，当一个组合求出后，进行计数，并将lista列表中的一个组合输出，因此①处语句为lista[k]＝i；当组合的第一个数字选定时，其余的数字是从余下的m－1个数中取k－1数的组合，即将求m 个数中取k个数的组合问题转化成求m－1个数中取k－1个数的组合问题，因此②处代码为comb(i－1，k－1)；③处代码的功能是调用递归函数comb，参数分别为n和r，因此，③处代码为comb(n，r)。课时2　迭代与递归
课时目标
1.通过实例分析，理解迭代和递归算法的基本思想，掌握利用迭代和递归算法解决问题的基本方法。2.能正确分析递归公式和递归结束条件，灵活使用迭代和递归算法解决实际问题，提升学生的计算思维。
1.迭代算法的概念
不断用变量的____________递推出__________的过程称为迭代算法。
2.利用迭代算法解决问题，需要考虑的三个方面
(1)确定____________。
(2)建立____________。
(3)控制____________。
迭代算法的难点在于寻找和建立正确的迭代公式，一般使用循环结构语句实现。3.递归算法的概念
一个函数在其定义中______________________来解决问题的方法称为递归算法。
递归算法的实质是：将规模大的问题分解成规模小的问题，然后从这些小问题的解中构造出大问题的解，并且这些规模较小的问题也能采用________的分解和综合方法。当递归到达某个________，如问题规模缩减为0或1时，能直接得解。
4.设计递归算法时，需要满足的两个条件
(1)确定____________。
(2)确定递归的__________(或称为边界条件)。
5.递归过程的两个阶段
(1)________：把较复杂的问题的求解递推到一些简单问题的求解。
(2)________：当获得最简单问题的解后，逐级返回依次得到稍复杂问题的解。
正确区分迭代算法和递归算法
(1)迭代是利用变量的旧值推算出变量的一个新值；而递归算法是指一个函数在其定义中直接或间接调用自身的一种方法，它通常把一个复杂的问题转化为一个与原问题相似的规模较小的问题来解决，可以极大地减少代码量，降低编程的难度。因此，迭代算法效率较高，而递归算法比较占用空间，程序运行效率较低。
(2)递归是自己调用自己，而迭代就是不断地调用赋值语句；递归中一定有迭代，但是迭代中不一定有递归，大部分情况下递归和迭代可以相互转换。
例1 让计算机重复执行一组指令(或一些步骤)，这组指令(或这些步骤)每执行一次时，都会将变量从原值递推出一个新值的算法是(　　)
A.递推算法 B.递归算法 C.迭代算法 D.查找算法
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　利用迭代算法处理问题时，其中从变量的前一个值推出其下一个值的公式的过程称为(　　)
A.确定迭代变量 B.设定迭代结束条件
C.控制迭代过程 D.建立迭代关系式
例2 丑数是指不能被2、3、5以外的质数整除的数。判断丑数的自定义函数程序如下：
def ugly(n)：
for i in [2，3，5]：
　　
return n＝＝1
若调用执行自定义函数ugly(30)，下列说法正确的是(　　)
A.函数返回值为False
B.方框处程序应用了迭代算法
C.该程序的时间复杂度为O(n2)
D.条件语句n%i＝＝0执行了3次
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　小明设计了一个算法求2n的值，算法思想是：先把2n转换为2*2n－1，而2n－1又可以转换为2*2n－1－1，如此继续，直到2*20，已知20＝1，再反过来，又依次求出21，22，…，直到求出了2n的值。小明求2n的值所采用的算法是(　　)
A.迭代算法 B.枚举算法 C.递归算法 D.解析算法
若在自定义函数中又出现调用自定义函数本身，则程序使用的是递归算法。而迭代算法是指迭代变量通过迭代关系，由旧值不断推出新值，从而求出问题的解。
例3 定义如下函数：
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
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　下列Python程序的功能是使用递归算法求ans的值。
def fx(n)：
if n＝＝0：
return　1
else：
return n*fx(n－1)
x＝int(input(″please input x：″))
ans＝fx(x)
print(ans)
程序执行时，输入x的值为5，则输出的结果为(　　)
A.24 B.32 C.120 D.720
例4 将十进制正整数转化为二进制数，对应的 Python 程序如下：
def toStr(n，base)：
　 s＝″01″
　 if n　return s[n]
　 else：
return ①________________
n＝int(input('请输入正整数：'))
result＝toStr(n，2)
print(result)
则代码中①处的语句可为(　　)
A.toStr(n∥base，base)＋s[n % base]
B.s[n % base]＋toStr(n∥base，base)
C.toStr(n % base，base)＋s[n∥base]
D.s[n∥base]＋toStr(n % base，base)
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　有如下Python程序：
def fx(x)：
if x>2：
return fx(x－1)*fx(x－2)
elif x＝＝1：
return 1
elif x＝＝2：
return 2
y＝int(input(″请输入y的值：″))
print(fx(y))
(1)该程序执行时，输入y的值为6时，输出的结果为__________；
(2)该程序执行时，输入y的值为8时，输出的结果为__________。
　　　　　　　　　　　　　
1.下列有关迭代算法和递归算法的描述，不正确的是(　　)
A.在使用递归算法时，必须有一个明确的递归结束条件，称为递归出口
B.一般来说，迭代算法效率较低，而递归算法效率较高
C.递归中一定有迭代，但迭代中不一定有递归
D.通常情况下，迭代算法和递归算法可以相互转换
2.在计算机内实现递归算法时所需的数据结构是(　　)
A.数组 B.栈 C.队列 D.链表
3.有如下Python程序段：
def f(x)：
　 if x＝＝1：
　return ″B″
　 else：
　 return str(1－(x%2))＋f(x－1)
L＝″″；i＝0
while i<10 ：
　 if i%2＝＝0 and i%3＝＝1：
　L＝L＋f(i)
i＝i＋1
print(L)
执行该程序段后，变量L的值是(　　)
A.010B B.101B C.B1101 D.B0010
4.有如下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
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.定义如下函数：有如下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
7.输入两个正整数，使用递归算法求这两个正整数的最大公约数。
具体算法为：给定两个整数，如果两个整数相等，则最大公约数是其本身；如果不相等，取两个整数的差和两个整数中较小的数比较，相等则为最大公约数，不相等则继续上面的算法，直到相等。
实现上述功能的Python程序如下，请回答下列问题。
def gcd(x，y)：
if ①________________：
return x
else：
small＝min(x，y)
②________________
a＝int(input(″输入第一个整数：″))
b＝int(input(″输入第二个整数：″))
print(gcd(a，b))
(1)请在程序划线处填入合适的代码。
(2)程序运行时，输入两个整数分别为24、56，则输出的结果为______________。
(3)若要输出两个整数的最小公倍数，则应在程序的最后增加的语句为____________。
课时2　迭代与递归
知识梳理
1.旧值　新值
2.(1)迭代变量　(2)迭代关系式　(3)迭代过程
3.直接或间接调用自身　同样　边界
4.(1)递归公式　(2)结束条件
5.(1)递推　(2)回归
例题精析
例1　C　[本题主要考查的是迭代算法的定义。本题中描述的算法是迭代算法，因此，答案为C。]
变式训练　D　[本题主要考查的是迭代算法的基本步骤。使用迭代算法的三个步骤为：确定迭代变量、建立迭代关系式、控制迭代过程，其中从变量的前一个值推出其下一个值的公式的过程称为建立迭代关系式。因此，答案为D。]
例2　B　[本题考查算法思想应用。题目中对丑数的描述等价于：丑数是指只能被2、3、5整除的数。A选项30＝2*3*5，30是丑数。B选项方框中程序为当n能被i整除时，不断求n除以i的商，是一个重复反馈的过程。C选项整个除的次数不会大于n，因此时间复杂度为O(n)。D选项除2、3、5过程中，一次能除通，一次条件不成立，条件语句n%i＝＝0执行了6次。]
变式训练　C　[本题主要考查的是递归算法的思想。本题中求2n的值，采用“大事化小，小事化了”的方法，符合递归算法的基本思想，因此答案为C。]
例3　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次。]
变式训练　C　[本题主要考查的是递归算法的程序实现。递归函数的功能是求n的阶乘(x！＝1*2*3*…*n)，因为输入的x的值为5，因此本程序是求5的阶乘，最后输出的结果为120，答案为C。]
例4　A　[利用递归的思想来处理十进制与其他数制的转换问题，函数功能是将每一次得到的余数作为结果逆序保存，整数部分再次利用函数进行转化，直到最后得到的整数部分小于要转换的进制数为止，转化过程结束。读程序可知，当 n变式训练　(1)32　(2)8192
解析　本题主要考查的是递归算法。(1)当y＝5时，fx(6)＝
fx(5)*fx(4)，fx(5)＝fx(4)*fx(3)，fx(4)＝fx(3)*fx(2)，
fx(3)＝fx(2)*fx(1)，而fx(2)＝1，fx(1)＝1，
因此，可求得fx(6)＝32；
(2)当y＝8时，fx(8)＝fx(7)*fx(6)，fx(7)＝fx(6)*fx(5)，因此可求得fx(8)＝8192。
随堂检测
1.B　[本题主要考查的是迭代算法和递归算法的特征。一般来说，迭代算法效率较高，而递归算法比较占用空间，程序运行效率较低，因此，答案为B。]
2.B　[栈的特点是先进后出，符合递归算法的思想，即在计算机内实现递归算法时使用栈数据结构，因此答案为B。]
3.B
4.C　[函数fun(34，4)＝fun(30，5)，而30%5的值为0，因此返回30。]
5.B　[程序的功能是判断字符串s是否是对称字符串。pd(″abcba″)返回pd(″bcb″)，pd(″bcb″)返回pd(″c″)，pd(″c″)返回True，因此调用3次。]
6.A　[程序的功能是辗转相除法计算两个非负整数的最大公约数。函数fab(4，8)返回fab(4，4)，函数fab(4，4)返回4。函数fab(8，4)返回4。]
7.(1)①x＝＝y　②return gcd(small，abs(x－y)) 或 return gcd(small，abs(y－x))　(2)8　(3)print(a*b∥gcd(a，b))
解析　本题主要考查的是递归算法的程序实现。(1)当两个整数相等时，最大公约数是其本身，因此①处的条件是x＝＝y；②处是递归调用，如果两个整数不相等，则取两个整数的差和两个整数中较小的数，重新求解这两个整数的最大公约数，因此②处代码为return gcd(small，abs(x－y))或return gcd(small，abs(y－x))。(2)整数24和56的最大公约数为8。(3)最小公倍数为a*b∥gcd(a，b)，因此，在程序的最后增加的语句为print(a*b∥gcd(a，b))。

展开更多......

收起↑