## 初探遞迴 作者：reset007 --- ## 回顧一下 第一堂課的Kahoot!題目... ----  ---- ### 所以遞迴到底是什麼?  --- ## 先來看看幾個例子 ---- ### 費氏數列 1, 1, 2, 3, 5, 8, ... ---- ### 定義 $F(1)=F(2)=1$ $F(n)=F(n-1)+F(n-2)$ ---- ### 定義 $F(1)=F(2)=1$ $F(n)=F(n-1)+F(n-2)$ 有注意到$F$在一條算式裡重複出現嗎? ---- ### 階乘 1, 2, 6, 24, 120, 720, ... ---- ### 定義 $0!=1$ $n!=n\times (n-1)!$ ---- ### 定義 $0!=1$ $n!=n\times (n-1)!$ 定義的等式中出現了兩個階乘!! --- ## 小結 我們稱「遞迴」是一個 **在自己的函式中呼叫自己的過程** --- ## 實作 以**費氏數列**為例 ---- 如果我們想知道$F(n)$是多少 我們需要先知道$F(n-1)$和$F(n-2)$ ---- ```cpp= int F(int n){ return F(n-1)+F(n-2); } ``` ---- ```cpp= int F(int n){ return F(n-1)+F(n-2); } ``` 這個程式不會停止 因為它會無止境地去呼叫比他更小的F 所以我們必須設定已知的終止條件 回顧一下定義 ----  把這兩項加到我們的自訂函式裡 ---- ```cpp= int F(int n){ if(n==1 or n==2)return 1; return F(n-1)+F(n-2); } ``` ---- ### 小問題 如果今天求F(30) 就會發現 這東西跑得有點慢耶 ----  ---- 光F(5)就要計算這麼多次了 ---- 於是一位偉大的演算法學者說了 ----  ---- ```cpp= //記憶化 int fibo[100000] = {0};//記憶用陣列 int F(int n){ if(fibo[n])return fibo[n];//直接讀記憶體 if(n==1 or n==2)return fibo[n] = 1;//初始條件 順便存在陣列裡 return fibo[n] = (F(n-1) + F(n-2));//遞迴式 + 記憶化 } ``` 多用一排陣列儲存已經算好的數 省去了重複計算的麻煩 --- ## 常見應用 嘗試用遞迴寫出這些題目! --- ## 求最大公因數 [A005 GCD的求解](http://mdcpp.mingdao.edu.tw/problem/A005) ---- ### 遞迴關係式 $\gcd(a, b)=\gcd(a \% b, b)$ 這東西就是我們國中學到的 **輾轉相除法** ----  ---- 想想看怎麼用遞迴實作ㄅ ---- code: ```cpp= int gcd(int a, int b){ if(a < b)return gcd(b, a);//先大後小 方便我們處理 if(b == 0)return a;//若有一方整除 代表另一個數即為所求 return gcd(b, a % b);//遞迴式 } ``` --- ## 碎形 [B003 分形練習](http://mdcpp.mingdao.edu.tw/problem/B003) ---- 先放個~~萊洛三角形~~謝爾賓斯基三角形給大家看 ----  ---- 圖太大了我懶得縮orz ---- ### 遞迴關係 小物件用某個規律組成中物件 中物件再用一樣的規律組成大物件 ---- 想想看怎麼用遞迴實作ㄅ ---- 虛擬code(編譯不會過): ```cpp= bool c[2500][2500];//陣列有可能太小 n太大時需要用別的方法處理 void draw(int level, int x, int y){ if(level == 1)c[x][y]=1;//把需要輸出X的位置標註起來 int length = pow(3, level-2); draw(level-1, x, y);//左上角 draw(level-1, x+length*2, y);//右上角 draw(level-1, x+length, y+length);//中間 draw(level-1, x, y+length*2);//左下角 draw(level-1, x+length*2, y+length*2);//右下角 } int main(){ ... draw(n, 0, 0);//從左上開始 for c://輸出答案 記得該換行要換 if(c[i][j] == 1)cout<<"X"; else cout<<" "; cout<<"---"; } ``` --- ## 進階應用 遞迴還可以用在哪? ---- - 暴力搜索(枚舉 aka 窮舉) - 圖的遍歷(DFS / BFS) - 動態規劃 aka DP - ...很多很多地方 ---- 先把基本功練熟吧 這樣未來遇到也會更得心應手! --- ## 回家功課 ---- 在MDjudge右邊的Tags點擊「遞迴」 ----  --- ## 謝謝大家