資源簡介

(共30張PPT)
5.2 迭 代 與 遞 歸 （二）
——遞 歸
冊 別：選擇性必修1
學 科：高中信息技術（浙教版）
學習目標：
能理解遞歸的算法思想。
能合理選用數據結構，理清遞歸公式及結束條件，遞歸的遞推與回歸兩個階段。
能用自然語言、流程圖、Python語言描述遞歸算法。
能掌握遞歸算法的一般設計思路。
能自覺應用遞歸算法，解決生活、學習中的問題。
引入：猜猜E娃娃有幾個銅幣？
2
3
A B C D E
我比前一個娃娃少2個銅幣！
我比前一個娃娃少2個銅幣！
我比前一個娃娃少2個銅幣！
我比前一個娃娃少2個銅幣！
我有20個銅幣！
引入：俄羅斯套娃
2
3
相傳俄羅斯民族有兩家表親相鄰，表兄妹童年相伴長大，后來表兄遠走它鄉，由于思念家鄉的表妹，每年做木娃娃，一年比一年做的娃娃大。數年后，他回到了家鄉，將娃娃送給了表妹，后人模仿傳稱套娃，又叫吉祥娃娃。
遞歸算法基本思想
通過函數自己調用自己來實現，也就是在其定義中直接或間接調用自身的方法，稱之為遞歸。
def tot(x):
if x<=1:
sum=1
else:
sum=x+tot(x-1)
return sum
print(tot(3))
直接調用
def t1(x):
if x<=1:
sum=1
else:
sum=x+tot(x-1)
return sum
def tot(y):
if y>20:
s=0
else:
s=y*t1(y)
return s
間接調用
算一算:小猴子第一天摘了多少個桃子
找出規律
天 10 9 8 … 2 1
桃子數t 1 (t(10)+1)*2 (t(9)+1)*2 (t(3)+1)*2 (t(2)+1)*2
有一天小猴子摘若干個桃子,當即吃了一半還覺得不過癮,又多吃了一個。第二天接著吃剩下桃子中的一半，仍覺得不過癮又多吃了一個，以后小猴子都是吃尚存桃子一半多一個。到第10天小猴子再去吃桃子的時候，看到只剩下一個桃子。問小猴子第一天共摘了多少個桃子
能用遞歸算法解決問題的特征
天 10 9 8 … 2 1
桃子數t 1 (t(10)+1)*2 (t(9)+1)*2 (t(3)+1)*2 (t2)+1)*2
為求解規模為N的問題，設法將它分解成規模較小的問題，然后從這些小問題的解中方便地構造出大問題的解，并且這些規模較小的問題也能采用同樣的分解和綜合方法。
當遞歸到達某個邊界，如問題規模縮減為0或1時，能直接得解。
遞歸的兩個條件
天 10 9 8 … 2 1
桃子數t 1 (t(10)+1)*2 (t(9)+1)*2 (t(3)+1)*2 (t2)+1)*2
if day==10:
tot=1
elif day!=10:
tot=(t(day+1)+1)*2
確定遞歸結束條件
確定遞歸公式
遞歸算法Python程序實現：
天 10 9 8 … 2 1
桃子數t 1 (t(10)+1)*2 (t(9)+1)*2 (t(3)+1)*2 (t(2)+1)*2
if day==10:
tot=1
elif day!=10:
tot=(t(day+1)+1)*2
確定遞歸結束條件
確定遞歸公式
def t(day):
return tot
print(t(1))
if day==10:
tot=1
elif day!=10:
tot=(t(day+1)+1)*2
遞歸算法的執行過程:
遞推：將復雜的問題（規模為n)的求解遞推出一些簡單的問題（規模小于n）的求解。此階段，必須有終止遞推的情況。
回歸：獲得最簡單情況的解后，逐級返回依次得到稍復雜問題的解。
天 10 9 8 … 2 1
桃子數t 1 (t(10)+1)*2 (t(9)+1)*2 (t(3)+1)*2 (t2)+1)*2
遞推
回歸
逐層調用，直到邊界（遞推）
代入計算，依次返回（回歸）
課堂小練：說說遞歸實現過程
def tot(x):
if x<=1:
sum=1
else:
sum=x+tot(x-1)
return sum
print(tot(3))
調用自身
1
2
3
4
5
6
7
7 print(tot(3))
1 def tot(3):
2 if x<=1 False
4 else:
5 sum=3+tot(2)
1 def tot(2):
2 if x<=1 False
4 else:
5 sum=2+tot(1)
1 def tot(1):
2 if x<=1 True
3 sum=1
(13)返回1
(14)返回3
課堂小練：表格形式展示遞歸實現過程
調用自身
執行(1)7 print(tot(3)) 計算tot(3)
計算tot(3) 執行5 sum=3+tot(2) 結果sum=3+3, return sum,返回6，調用tot(3)結束
計算tot(2) 5 sum=2+tot(1) 結果sum=2+1, return sum,返回3，調用tot(2)結束
計算tot(1)； 執行2 if x<=1 （True） 3 sum=1 return sum 調用返回1，tot(1)調用結束
調用
調用
調用
返回
返回
返回
遞歸實現要點:
（1）有明確的結束遞歸的邊界條件（終止條件）及終止時的邊界值。
（2）函數的描述中包含其本身。
def tot(x):
if x<=1:
sum=1
else:
sum=x+tot(x-1)
return sum
print(tot(3))
def t(day):
if day==10:
tot=1
elif day!=10:
tot=(t(day+1)+1)*2
return tot
print(t(1))
課堂實踐：用遞歸算法求 n 的階乘
1、抽象建模
利用遞歸算法求n的階乘（n!=1×2×…n-1×n）。由數學知識可知，n階乘的遞歸定義為：它等于n乘以n-1的階乘，即n！=n*(n-1)!,并且規定0和1的階乘為1。設函數fac(n)=n!，則fac(n)可表示為：
fac(n)=
1 n=0或n=1
n*fac(n-1) n>0
課堂實踐：用遞歸算法求 n 的階乘
2、設計算法
開始
n<=1
輸入n
輸出n!
函數fac←n*fac(n-1)
結束
N
Y
函數fac←1
用遞歸算法求 n 的階乘程序實現:
def fac(n):
if n<= 1:
return 1
else:
return n * fac(n - 1)
#遞歸函數
#結束遞歸的邊界條件（終止條件）
#結束遞歸的終止時的邊界值
#繼續
#遞歸調用
x=int(input())
print(fac(x))
3、編寫程序,并上機調試
思考:遞歸的作用
1、分解成規模較小的同類型問題。
n!=n*(n-1)!
2、用遞歸函數替代多重循環。
3、解決本來就是用遞歸形式定義的問題。
課堂小練：（填空）
#1、如求第10項
#2、遞歸函數fx
#3、遞歸結束條件n<2
def fx(n):
if n<2:
（1）
else:
（2）
return f
print（fx(10))
用遞歸算法求裴波那契數列為：1，1，2，3，5，8，13 ……
f(n)=
1 n<=1
f(n-1)+f(n-2) n>=2
#4、遞歸結束值
#5、遞歸表達式，自己調用自己
f=1
f=fx(n-1)+fx(n-2)
1
2
3
4
5
6
7
課堂小練：
一個樓梯有n階，上樓可以一步上一階，也可以一步上二階。要求：編寫一個程序，輸入一個正整數n(表示樓梯階數)，輸出共有多少種不同的走法可以到達第n階。
2.程序設計并調試：
f(n)=
1 n=1
2 n=2
f(n-1)+f(n-2) n>=3
用遞歸編程實現：
def fx(n):
if n == 1 or n == 2:
return n
else:
return fx(n-1)+fx(n-2)
n=int(input("臺階數量:"))
print(“臺階走法:”,fx(n))
#1、如求第臺階走法
#2、遞歸函數fx
#3、遞歸結束條件n<=2
#4、遞歸結束值
#5、遞歸表達式，自己調用自己
1
2
3
4
5
6
7
比較迭代與遞歸：
迭代 遞歸
初始值 終止值
迭代表達式 遞歸表達式
終止條件 終止條件
循環實現 遞歸函數實現
臺階走法迭代程序：
n=int(input("臺階數量："))
a=1;b=2
for i in range(3,n+1):
c=a+b
a=b
b=c
if n==1 or n==2:
print(n)
else:
print(c)
臺階走法遞歸程序：
def fx(n):
if n == 1 or n == 2:
return n
else:
return fx(n-1)+fx(n-2)
n=int(input("臺階數量:"))
print(“臺階走法:”,fx(n))
思考：遞歸程序一般結構：
def fx(n): #遞歸函數
if n == 1 or n == 2: #結束遞歸的邊界條件
return n #結束遞歸的值
else:
return fx(n-1)+fx(n-2) #遞歸表達式（調用自己）
1
2
3
4
5
漢諾塔游戲： 教材P124
1. 抽象與建模
為了將n個圓盤從A柱經過B柱移動到C柱，可建立如下模型：
將n-1個圓盤從A柱經過C柱移動到B柱
將A柱中剩下的一個圓盤移動到C柱
將n-1個圓盤從B柱經過A柱移動到C柱
得出關鍵點：注意最下面的圓盤
2.設計算法
（1）定義一個實現圓盤移動的函數move。如將n個圓盤從A柱經過B柱移動到C柱，可調用函數move(n, a, b, c)，其中，n表示A柱上的圓盤個數，a、b、c分別表示A柱、B柱、C柱。
（2）將n-1個圓盤從B柱經過A柱移動到C柱，可以分解成如下遞歸調用：
move(n-1, a, c, b)
a→c
move(n-1, b, a, c)
（3）當n=1時，直接移動圓盤，遞歸結束。
漢諾塔游戲： 教材P124
if(n == 1):
print(a,"->",c)
return
move(1, a, b, c)
漢諾塔游戲： 教材P124
3.編寫程序
拓展學習：
遞歸與棧
程序 測試效果
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(3, "A", "B", "C") A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
根據算法，得到的程序及測試效果如下：
課堂小結
遞歸算法的概念
算法思想 算法描述
遞歸算法的兩個條件和兩個階段
遞歸算法的數學原理與注意事項
程序實現
學習評價
對自己的表現進行客觀的評價，并思考后續完善的方向。（3=優秀，2=一般，1=仍需加油）
評分項 自我評價
能計算小猴摘桃并總結遞歸算法的基本思想 3 2 1
掌握遞歸算法的兩個條件和兩個階段 3 2 1
能自主學習教材并用自然語言、Python語言描述遞歸算法 3 2 1
能夠編程實現斐波那契數列、階乘的遞歸實現 3 2 1
掌握遞歸算法的設計思路，理解其數學原理和注意事項 3 2 1
能用遞歸算法解決學習、生活中的應用 3 2 1
課后作業
1.求最大公約數：早在公元前300年左右，歐幾里得就在他的著作《幾何原本》中給出了高效的解法——輾轉相除法。
輾轉相除法的方法是用較大的數X除以較小的數Y，得到余數Z
如果余數為0，則較小數Y就是兩者的最大公約數。
例如：33和9 的最大公約數就是9與6的最大公約數3
以下程序#號劃線處代碼為（ ）
A.a B. gcd(b,a%b)
C. gcd(b,a//b) D. gcd(b,a)
B
def gcd(a,b):
if a%b==0:
return b
else:
return ##
m,n=map(int,input().split())
Print(gcd(m,n))
課后作業
2. def zh(n):
if n<=1:
f='1'
else:
f=zh(n//2)+str(n%2)
return f
print(zh(18))
該程序段運行后的輸出值為( )
A、10100 B、10010 C、11010 D、11000
B
課后作業
3.有如下數列a1,a2,a3,…的定義如下:
a1=1,a2=1 ,…,an =3an-1+2an-2(n>2)。為求該數列的第n項值,現利用遞歸算法實現,Python代碼如下,請在劃線處填入合適的代碼。
def yuan(x):
if x<=2 :
return ①
else :
②
n=int(input(“n=“))
print(yuan(n))
1
② return 3*yuan(x-1)+2*yuan(x-2)

展開更多......

收起↑