資源簡介

(共17張PPT)
第3課 遞歸算法
目 錄
1
遞歸算法原理
Principle of recursive algorithm
2
遞歸算法設計與分析
Recursive algorithm design
3
遞歸算法設計實例
Recursive algorithm design example
4
總結
Summary of recursive algorithm
第一章
遞歸算法原理
游戲引入：比比誰算的快
游戲規則：
1、讓5位同學排成一隊，從第一位同學開始，依次按順序，每位同學給出一個關于自己身高的提示。
2：第一位同學說比第二位同學高2厘米；第二位同學說比第三位同學高2厘米；第三位同學說比第四位同學高2厘米；第四位同學說比第五位同學高2厘米；第五位同學說他170厘米。
請問這5位同學的身高分別是多少？比一比，哪個小組算的更快，并派小組代表說說你們小組是怎么算出來的。
游戲啟發
第5位同學的身高。
解決該問題的出發點和已知條件分別是什么
H5=170cm，H4=H5+2，H3=H4+2，H2=H3+2，H1=H2+2。
前后相鄰兩人在身高上有什么樣的數量關系 最好用數學關系式表示出來。
function (求當前同學身高)
{
if(是第五位同學)
身高是170cm；
else 身高=后一位同學+2cm；
}
把剛剛求解每位同學身高的問題，從自定義函數的角度用偽碼來描述呢？
游戲啟發
回到剛剛求身高的問題，我們發現由求第1個人身高的問題轉化為求第2個人身高的問題，最后到求第5個人身高的問題，該階段為遞推階段。從第5個人的已知身高推算出第4個人的身高，一直到推算出第1個人的身高的階段為返回階段。遞推階段和返回階段共同構成遞歸過程。
利用一個已知數一步步進行推算的方法，就是遞歸法。
1：問題的初始條件是H(5)=170厘米，終止條件是求到第5位同學就可以不用求了。
2：H(n)和H(n+l)的關系是：H(n)=H(n+1)+2。
假設用n表示第n個人，用函數H(n)表示第n個人的身高，提出問題：
1：遞歸的初始和終止條件分別是什么
2：H(n)和H(n-l)的關系是什么
原理及特點介紹
定義一個方法時，出現本方法調用本方法的過程，稱之為遞歸。
遞歸的概念
1.必然有一個邊界值
2.使用遞歸代碼往往更加簡潔，可讀性強。
遞歸的特點
需要解決的問題可以轉化為一個或多個子問題來求解，而這些子問題的求解方法與原問題完全相同，只是在數量規模上不同。
遞歸調用的次數必須是有限的。
必須有結束遞歸的條件來終止遞歸。
遞歸解決的問題應該滿足以下三個條件：
第二章
遞歸算法設計與分析
遞歸算法設計
根據前面所講“滿足遞歸解決問題的條件” ，我們設計遞歸算法來求剛剛游戲中的身高問題
C++代碼實現如下：
int height(int n)
{
if(n==5)
return 170;
else
return height(n+1)+2;
}
比較分析
普通實現方式與遞歸實現方式比較：
通過比較發現：
遞歸算法具有一個邊界條件n=5，當滿足n為5，返回自身
遞歸算法的返回值有兩種情況，滿足邊界值返回特定值，不滿足邊界條件，返回自身調用自身的形式
非遞歸算法沒有明確的邊界值條件，但利用了for循環，隱式地傳達了邊界值，i>=時不再相加
非遞歸算法還建立了數組a，用來記錄每位同學的身高
設計結論
從以上過程可以得出：
每遞歸調用一次，就需進棧一次，最多的進棧元素個數稱為遞歸深度，當n越大，遞歸深度越深，開辟的棧空間也越大。
每當遇到遞歸出口或完成本次執行時，需退棧一次，并把當前棧頂保留的值送回相應的參量中進行恢復，當全部執行完畢時，棧應為空。
height(1)
height(2)
height(3)
height(4)
height(5)=170
height(4)=height(5)+2=172
height(3)=height(4)+2=174
height(2)=height(3)+2=176
height(1)=height(2)+2=178
分
解
過
程
求
值
過
程
第三章
遞歸算法設計實例
經典遞歸算法實例
兔子出生以后兩個月就能生小兔，如果每月生一次恰好生一對小兔（雌雄各一對），且出生的兔子都能成活。試問：由1對小兔開始，一年后有多少對兔子，兩年后共有多少對兔子。
問題
在第0月有1對兔子；第一月也只有1對兔子；在第2月這對兔子生了1對小兔，公兩對兔子；在第3月，老兔子又生了1對兔子，共3對兔子；在第4個月，老兔子和第2個月出生的兔子各生了一對小兔，共五對兔子；在第5個月，第3個月的3對兔子各生了一對兔子，共8對兔子；在第6個月，第4個月的5對兔子各生了一對兔子，共13對兔子…以此類推
思路
經典遞歸算法實例
而斐波那契數就是用來描述一組具有兔子總數規律的數列，他具有的特征就是從第3項起，每個數都是前兩個數之和。
C++中斐波那契數的實現：
不難得兔子數量和月數之間的關系：
第四章
總結
總結
使用遞歸首先要滿足遞歸的條件，必須有結束遞歸的條件來終止遞歸，并且遞歸的次數是有限的。
一個正確的遞歸程序雖然每次調用的是相同的子程序，但它的參量和局部變量均不相同。
因為系統在每一次調用時開辟一組存儲單元，用來存放本次調用的返回地址以及被中斷的函數的參量值，所以這就保證了重復調用執行時的獨立性。
隨著調用的不斷深入，到達出口時，不再執行遞歸調用而終止函數的執行。
謝謝觀看！

展開更多......

收起↑