資源簡介

(共63張PPT)
課時2　迭代與遞歸
第五章　數據結構與算法
1.通過實例分析，理解迭代和遞歸算法的基本思想，掌握利用迭代和遞歸算法解決問題的基本方法。2.能正確分析遞歸公式和遞歸結束條件，靈活使用迭代和遞歸算法解決實際問題，提升學生的計算思維。
目 錄
CONTENTS
知識梳理
01
例題精析
02
隨堂檢測
03
鞏固與提升
04
知識梳理
1
1.迭代算法的概念
不斷用變量的______遞推出______的過程稱為迭代算法。
2.利用迭代算法解決問題，需要考慮的三個方面
(1)確定____________。
(2)建立_______________。
(3)控制____________。
迭代算法的難點在于尋找和建立正確的迭代公式，一般使用循環結構語句實現。
舊值
新值
迭代變量
迭代關系式
迭代過程
3.遞歸算法的概念
一個函數在其定義中___________________________來解決問題的方法稱為遞歸算法。
遞歸算法的實質是：將規模大的問題分解成規模小的問題，然后從這些小問題的解中構造出大問題的解，并且這些規模較小的問題也能采用______的分解和綜合方法。當遞歸到達某個______，如問題規?？s減為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?。?*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]?。絪[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?。?：
if ①________________：
　　　　x＝x*3＋1
(1)請在程序劃線處填入合適的代碼。
(2)程序執行時，輸入x的值為120，則運算次數為__________。
答案　(1)①x % 2＝＝1 或x % 2?。?
②x＝x∥2?、踤＋＝1 或 n＝n＋1　(2)20
解析　本題主要考查的是迭代算法的程序實現。(1)本題使用的是迭代算法，當自然數變為1時，循環結束，否則，若x為奇數時，x＝n*3＋1，因此，①處代碼為x % 2＝＝1或x % 2?。?；若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.遞歸算法的概念
一個函數在其定義中______________________來解決問題的方法稱為遞歸算法。
遞歸算法的實質是：將規模大的問題分解成規模小的問題，然后從這些小問題的解中構造出大問題的解，并且這些規模較小的問題也能采用________的分解和綜合方法。當遞歸到達某個________，如問題規?？s減為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]?。絪[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?。?*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?、趓eturn 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))。

展開更多......

收起↑