###### tags: `MDCPP講義` # 遞迴 ---- 熟悉的名詞? ---- 高中數學課本2 第一章  ---- 就像數學課本上寫到的 遞迴的關係式長得像這樣 - $a_1 = 7$ - $a_n = a_{n-1} -2$ 出來變成 7、5、3、1、-1... ---- - $a_1 = 7$ - $a_n = a_{n-1} -2$ 首先來觀察這個式子 我們可以發現數學上的遞迴有兩個主要的特徵 1. 有一個初始的值 2. **透過自己本身來定義自己** ---- **透過自己本身來定義自己** 就是遞迴的精華所在 程式上的遞迴也是取其特性 ---- 我們先來看一下，程式上的遞迴長怎樣 ---- ```cpp= int f(){ return f(); } ``` 剛剛學完自訂函式: 蛤，一個函式呼叫自己是尛(ㄇㄚˊ) ---- 不過他是一個正確的語法喔 更具象化描述他的話像是這樣 ----  ---- 明確一點的定義: 數學上：函數直接或間接已自己定義自己 程式上：一個函數會直接或間接的呼叫自己 ---- 這邊我們直接用栗子來講吧 ---- 現在有一個數列 1+2+3+4...+10 要計算出結果 ---- 直覺想到用迴圈解吧 ---- 這就是重點! 迴圈能做到的事情 遞迴大部分能做到 遞迴能做到的事情 迴圈大部分能做到 ---- 既然這樣我們為甚麼要學遞迴呢? ---- 在程式設計中 我們會有用到不同技術的時候 某些技術用遞迴會很好寫，用迴圈很難寫 ---- 會到1+2+3...+10的問題 ---- ```cpp= int main(){ int ans=0; for(int i=1;i<=10;i++) ans = ans+i; cout<<ans; } ``` ```cpp= int f(int x){ return f(x-1)+x; } int main(){ cout<<f(10); } ``` ---- 可以發現我們在下面引入的時候是從10開始 是因為我們的遞迴會一直往下呼叫自己 最後才算出自己的值 ```cpp= int f(int x){ if(x==1) return 1; return f(x-1)+x; } int main(){ cout<<f(10); } ``` ---- ```cpp= int f(int x){ if(x==1) return 1; return f(x-1)+x; } int main(){ cout<<f(10); } ```  --- ## 最經典的遞迴示範題 ---- [費氏數列](http://mdcpp.mingdao.edu.tw/problem/B001) ---- 之前我們都練習過費氏數列 也有人寫過我出的那題費波那契湯   ---- 但我相信你們很熟費氏數列了! ---- 所以我們就直接開始 ---- 求費氏數列的第6位是多少 ---- $a_n = a_{n-1} + a_{n-2}$ ---- A1:直接數 1 1 2 3 5 8 ---- A2:迴圈解 ```cpp= int f[10]; f[1]=1 f[2]=1 for(int i=3;i<=6;i++) f[i] = f[i-1]+f[i-2]; ``` ---- A3:遞迴解 ```cpp= int f(int x){ if(x==1 || x==2) return 1; // 這是費氏數列的預設兩個數值 return f(x-1)+f(x-2); // 費氏數列的前兩項相加變後一項 } int main(){ cout<<f(6);//首先這裡一樣用到我們先從大數字開頭 //往下呼叫到小數字之後再推回來 } ``` ---- 圖解  ---- 觀察圖片會發現 我們重複呼叫某個函式好幾次 這樣就會變得很慢 ---- 所以我們要來講一個優化他的方法 ---- ## 記憶化 ---- 所謂的記憶化 在1940年就由我們的老蔣提出來了  ---- 記憶化就是 ~~打不贏就遷首都烙跑，等別人來救~~ ---- 其實是  ---- 什麼叫以空間換取時間? ----  這張圖上有許多重複的地方，如果每呼叫一次就要重做一次 那顯然要非常久 ---- 所以我們可以把每次做完的結果記錄下來 當我們在遇到他的時候，就可以直接把記下來的東西拿出來 就不用在重新做一次了 **讚嘆老蔣的智慧** ---- 寫成程式就是這樣 ```cpp= int mem[10] //memory mem[1]=1,mem[2]=1 int f(int x){ if(mem[x]!=0) return mem[x]; // 當我們記憶的東西存在，就取出來用 mem[x] = f(x-1)+f(x-2); return mem[x]; // 費氏數列的前兩項相加變後一項 } int main(){ cout<<f(6);//首先這裡一樣用到我們先從大數字開頭 //往下呼叫到小數字之後再推回來 } ``` ---- 我們實際只會走過這幾個點 這樣就快許多了  --- ## 一樣經典的題目 ---- GCD(最大公因數) ---- 程式中常見的最大公因數求法 就是以前教的輾轉相除法 ---- 複習一下 ```cpp= 輾轉相除法 | 540 | 840 | 1 | 300 | 540 | 1 |-----|-----| | 240 | 300 | 4 | 240 | 240 | 1 |-----|-----| | 0 | 60 | ``` ---- 兩邊一直除來除去 如果a大，就用a/b取餘數 b大則反之 最後其中一個剩0 另外一個就是最大公因數了 ---- 把除過一遍的東西在拿來用新的方式除一遍 感覺非常的遞迴 ---- 具體來看一下程式碼 ```cpp= int gcd(int a,int b){ if(b == 0) return a; return gcd(b,a%b); } ``` 就這樣，他是對的 如果對於比較誰大誰小有疑惑的話 你會發現只要a的位置一開始放比較大的值 之後就會是a,b依序交換大小，第三行那才把a,b位置交換 左邊的數字就恆大 ---- 不過我們有個更快的方法 ```cpp= cout<<__gcd(a,b); ``` 就醬，C++其實有內建，所以很少會自己寫 不過你們還是可以練習一下用遞迴寫 ---- 事實上這應該是算法班的內容 不過你們學得很快，所以我們就先教了 ---- 再更深的內容，就等下學期，到算法班在一起學習吧 如果想更深入研究，也可以看看這份講義: https://hackmd.io/@jerryliu1029/HJWwNDsbc#/ ---- 感謝各位  ----