資源簡介

(共19張PPT)
遞歸
1 遞歸的概念
3 遞歸算法的設計方法
遞歸
2 遞歸算法的執(zhí)行過程
遞
歸
（把問題不斷分解為可操作性的小問題）
（把小問題的結(jié)果返回給大問題，達到最終目的）
遞歸
終結(jié)條件
大問題的解決中嵌套著與原問題相似的規(guī)模較小的問題，這種問題的解決方法在計算機科學中稱為遞歸，它通過函數(shù)自己調(diào)用自己來實現(xiàn)，即一個函數(shù)在其定義中直接或間接調(diào)用自身的一種方法。
遞歸的概念
階乘的定義：一個正整數(shù)的階乘是所有小于及等于該數(shù)的正整數(shù)的乘積。
遞歸算法的執(zhí)行過程——求階乘
n！= n*（n-1）！
n ！= n *（n-1）*…*2*1
（n-1）！= （n-1）*…*2*1
遞歸規(guī)律
1 （n=1）
f（n）=
n*f（n-1 ）（ n>1 ）
def f (n):
if n == 1:
return 1
else:
return n* f（n-1 ）
print(f(5))
f（5）=5*f （4）
f（4）=4*f （3）
遞推
f（3）=3*f （2）
遞推
f（2）=2*f （1）
遞推
f（1）=1
遞推
5！=？
回歸：1
1
回歸：2
2
回歸：6
6
回歸：24
24
def f (n):
if n == 1:
return 1
else:
return n* f（n-1 ）
print(f(5))
5！=120
遞歸=遞推+回歸
遞歸算法的執(zhí)行過程——求階乘
操作演示
遞歸算法的設計方法
把原問題分解成若干個相對簡單且類型相同的小問題，這樣復雜的原問題就變成相對簡單的子問題，而簡單到一定程度的子問題可以直接求解，最終原問題就可以通過遞推得到解答。
設計方法
1.能夠歸納出恰當?shù)倪f歸公式。
2.必須要有一個明確的遞歸終止條件。
探究活動——求解斐波那契數(shù)列
一對剛出生的小兔子，一個月后就能成長為成年兔，再過一個月后(即第三個月起)就每月生一對兔子。新生的兔子也按這個規(guī)律繁殖。
現(xiàn)在僅有一對剛出生的小兔子，問在沒有兔子死亡的情況下，一年后總共繁殖成多少對兔子。
意大利數(shù)學家斐波那契
分析表 一月
二月
三月
四月
五月
1對
2對
3對
5對
1對
分 析 表 1月 2月 3月 4月 5月 6月 7月 8月 9月 10月 11月 12月
小兔 1 1 1 2 3 5 8 13 21 34 55
大兔 1 1 2 3 5 8 13 21 34 55 89
合計 1 1 2 3 5 8 13 21 34 55 89 144
+
=
+
=
+
=
+
=
+
=
+
=
+
=
+
=
+
=
+
=
數(shù)列規(guī)律：從第三項開始,后面的數(shù)總是前兩數(shù)之和
數(shù)列規(guī)律：從第三項開始,后面的數(shù)總是前兩數(shù)之和
遞歸終結(jié)條件
def f(n)：
if n == 1 or n == 2:
return 1
else:
return f(n-1) + f(n-2)
print(f(12))
分 析 表 1月 2月 3月 4月 5月 6月 7月 8月 9月 10月 11月 12月
小兔 1 1 1 2 3 5 8 13 21 34 55
大兔 1 1 2 3 5 8 13 21 34 55 89
合計 1 1 2 3 5 8 13 21 34 55 89 144
+
=
1 n=1
1 n=2
f(n-1) + f(n-2) n>2
f(n)=
遞歸公式
def f(n)：
if n == 1 or n == 2:
return 1
else:
return f(n-1) + f(n-2)
print(f(5))
斐波那契數(shù)列求解的執(zhí)行過程
主程序f(5)
函數(shù)f(4)
函數(shù)f(3)
函數(shù)f(3)
函數(shù)f(2) =1
函數(shù)f(2) =1
函數(shù)f(1)=1
函數(shù)f(2)=1
函數(shù)f(1)=1
操作演示
知識拓展——斐波那契數(shù)列螺旋線
斐波那契螺旋線也稱為“黃金螺旋線”，是以斐波那契數(shù)列數(shù)字為半徑，連續(xù)繪制圓弧得到的螺旋線。
知識拓展——斐波那契數(shù)列螺旋線
課堂小結(jié)
遞歸
遞歸的概念
把問題轉(zhuǎn)化為規(guī)模較小的同類子問題，通過函數(shù)自己調(diào)用自己來實現(xiàn)。
遞歸算法
的執(zhí)行過程
遞歸算法
的設計方法
先傳遞，再回歸
1.能夠歸納出恰當?shù)倪f歸公式。
2.必須要有一個明確的遞歸終結(jié)條件
謝謝

展開更多......

收起↑