函式遞迴 - HackMD

# 函式遞迴先簡單複習一下函式 ```cpp= int fun(int a) { return a + a; } int main() { cout << fun(5) << endl; } ``` \ 函式呼叫自己的行為稱為遞迴，以下為範例: ```cpp= #include<bits/stdc++.h> using namespace std; void fun(){ cout << "執行一次" << endl; fun(); } int main(){ fun(); return 0; } ``` :::spoiler 輸出結果執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次執行一次 ...... ::: \ 很顯然會爆炸(Runtime Error)，所以要在內部設置終止條件: ```cpp = #include<bits/stdc++.h> using namespace std; int cnt = 0; void fun(){ cout << "執行一次" << endl; if(cnt < 10){ cnt++; fun(); } } int main(){ fun(); return 0; } ``` :::spoiler 幾次? 11次 ::: \ 當然你也可以利用函式的輸入來達成限制次數的目的: ```cpp = #include<bits/stdc++.h> using namespace std; void fun(int cnt){ cout << "執行一次" << endl; cnt++; if(cnt < 10){ fun(cnt); } } int main(){ fun(0); return 0; } ``` :::spoiler 幾次? 10次 ::: \ 以上的程式都是在進入函式時輸出，而函式結束時當然也可以輸出文字: ```cpp = #include<bits/stdc++.h> using namespace std; void fun(int cnt){ cout << "執行第" << cnt << "次" << endl; if(cnt < 5){ cnt++; cout << "進入第" << cnt << "次" << endl; fun(cnt); cout << "第" << cnt << "次執行結束" << endl; } } int main(){ fun(1); return 0; } ``` :::spoiler 執行幾次?進入幾次?執行結束幾次? (5,4,4) ```cpp= 執行第1次進入第2次執行第2次進入第3次執行第3次進入第4次執行第4次進入第5次執行第5次第5次執行結束第4次執行結束第3次執行結束第2次執行結束 ``` ::: \ 以上的函式都是void型態(一個空的變數型態)，所以要return空值，而如果函式是其他的資料型態，則要return**相對應**的資料型態，例如int: ```cpp= #include<iostream> using namespace std; int power(int a, int b){ if(b == 0){return 1;} return a * power(a, b-1); } int main(){ cout << power(3, 5); return 0; } ``` :::spoiler 輸出結果 243 ::: \ 要注意函式輸入的資料型態**不一定**要和輸出型態一樣(如前面輸入int回傳void) ### 簡單的遞迴程式 1.$a^n$ ```cpp= #include<iostream> using namespace std; int mod = 1e9+7; long long power(int a, int n){ if(n == 0) return 1; return a * power(a, n - 1) % mod; } int main(){ int a, n; while(cin >> a >> n){ cout << power(a, n) << endl; } return 0; } ``` Complexity: $O(n)$ \ 2. $n!$ ```cpp= #include<iostream> using namespace std; int mod = 1e9+7; int fac(int n){ if(n == 0) return 1; return n * fac(n - 1) % mod; } int main(){ int n; while(cin >> n){ cout << fac(n) << endl; } return 0; } ``` Complexity: $O(n)$ \ 3. Fibonacci Numbers ```cpp= #include<iostream> using namespace std; int mod = 1e9 + 7; int fib(int n){ if(n == 0){ return 0; } else if(n == 1){ return 1; } return (fib(n - 1) + fib(n - 2)) % mod; } int main(){ int n; while(cin >> n){ cout << fib(n) << endl; } return 0; } ``` Complexity: $O({\varphi}^{n})$ \ 以上三種操作的複雜度都**超爛** $a^n$ 會用fast_me實作(本章底部) 階乘會用陣列儲存(不須重複計算) 費氏數列的第n項會用matrix_fast_me實作(遙遠的未來會教) 上面的程式只是大概讓各位了解遞迴的運作,解題時千萬不要衝動 ## 實作GCD 題目:計算兩數的GCD(最大公因數) \ 想法:**輾轉相除法** \ 假設一個函式 $gcd(a,b)$ 來代表在輾轉相除法同一層的數字，且 $a>b$ ，則: ![](https://i.imgur.com/rafOUiK.png) 則可以看出下一層的數字為$(b, a\ mod\ b)$才能維持$a>b$, 且若$b=1$,則$a$為兩數的 gcd \ 若$a<b$，所以要將兩數交換位置，如下圖 ![](https://i.imgur.com/BSVxPG9.png) \ 因為$a\ mod\ b \equiv a \ (mod \ b)$，所以下一層的數字也可以表示為$(b, a\ mod\ b)$ :::success 嘗試寫出屬於你們自己的gcd程式吧! ::: [**a158: 11827 - Maximum GCD**](https://zerojudge.tw/ShowProblem?problemid=a158) [**a024: 最大公因數(GCD)**](https://zerojudge.tw/ShowProblem?problemid=a024) :::spoiler 程式碼(寫完再看) ```cpp= #include<iostream> using namespace std; int gcd(int a, int b){ if(b == 0){ return a; } else{ return gcd(b, a % b); } } int main(){ int a, b; while(cin >> a >> b){ cout << gcd(a, b) << endl; } return 0; } ``` ::: #### 三元運算子(額外補充)(邪教) ```cpp= if(a == 0){ cout << "true" << endl; } else{ cout << "false" << endl; } ``` 可以寫成: ```cpp= cout << (a == 0 ? "true" : "false") << endl; int b = ( 5 % 3 == 2 ? 5 : 7); //(條件式?如果條件式=true執行:如果條件式=false執行) ``` 所以上面gcd的程式又可以寫成: :::spoiler 程式碼(寫完再看) ```cpp= #include <iostream> using namespace std; int gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b); } int main(){ int a, b; while(cin >> a >> b){ cout << gcd(a, b) << endl; } return 0; } ``` ::: \ 是不是變得超短的?gcd簡單啦 :::spoiler but...gcd之後都是這樣做的 ```cpp= #include <bits/stdc++.h> using namespace std; int main(){ int a, b; while(cin >> a >> b){ cout << __gcd(a, b) << endl; } return 0; } ``` ::: :::danger 但還是請先實作一次遞迴gcd! ::: ## 快速冪快速冪，簡稱fastpow，也可以叫做fast_me 是有效的計算$a^b$的方法(a不一定要是整數)，但要是可以進行乘法的資料型態。 ==想法:== \ 定義$a^b$ = power(a, b); \ if $b = 0,a^b = 1$ \ if $b\equiv 0\ (mod\ 2) \ , a^b = a^{\frac{b}{2}}\times a^{\frac{b}{2}}$ \ if $b\equiv 1\ (mod\ 2) \ , a^b = a\times a^{\frac{b}{2}}\times a^{\frac{b}{2}}$ 注意這裡的$\frac{b}{2}$都是無條件消去(程式內部除法) \ 利用遞迴的方式先做出下一層的解，回傳後再計算並向上回傳數字會太大，所以計算過程記得取模 :::success Make your own fast_me! ::: :::spoiler 提示與注意事項 \ 1.遞迴時要注意不要遞迴(計算)兩次 $a^{\frac{b}{2}}$,直接平方就好 2.要記得開long long ::: :::spoiler 程式碼(寫完再看) ```cpp= #include<iostream> using namespace std; int fast_me(int a, int b, int mod){ if(b == 0){return 1;} long long c = fast_me(a, b/2, mod); c = c * c % mod; return b % 2 == 0 ? c : c * a % mod; } int main(){ int m,n; while(cin >> n >> m){ cout << fast_me(n, m, 1e9+7) << endl; } return 0; } ``` ::: [**Check if your code is right**](https://cses.fi/problemset/task/1095)