資源簡介

專題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″。

展開更多......

收起↑