# 函式 (Function) ---- ## 首先，什麼是函式? ---- 函式是一種將特定程式碼區塊**封裝**起來 可重複使用的單元 它能接收輸入（參數），執行特定任務 最後可選擇性地回傳一個結果。 ---- 通常在C++編譯並執行時 會優先執行名為main() 的函式 我們稱之為**主函式** 也就是我們熟悉的 ```C++ int main(){} ``` 其他的就叫做副函式 ---- 副函式可以使我們debug更方便 程式碼看起來也會比較整齊 我們今天統稱副函式為函式 ###### 這樣少打好多字，oh yeah --- ## 函式的格式 ---- 函式的格式長這樣: ```C++ 函式回傳的類別 函式名稱 (傳入的參數) { 函式內容 return... } ``` ---- 函式回傳的類別是自訂的 ```C++ int, bool, void(不會回傳任何東西) ``` ---- 而函式的宣告跟變數相同，不能衝突 而且要先宣告才能用 ```C++ //錯誤示範 int main() { sayhello(); } void sayhello() { cout << "HELLO!!"; } ``` 像這樣就會報錯!!! ---- 另外關於傳參的部分 可以想像成 將傳入的變數的值複製起來運算 ---- for example: ```C++ int plus(int a, int b) { //將main的a的值複製到plus的a //將7複製到b //注意這邊的a跟b是"獨立"的，也就是說:就算這邊改變plus的a的值也不會影響到main的a return a+b; } ``` 這個函式會回傳a+b ```C++ int a=6; cout << plus(a, 7); //輸出13 ``` --- ## 引用(Reference) ---- 今天天氣不錯，所以你寫了一個交換兩數的函式 ```C++ void sw(int a, int b) { int tmp=a; a=b; b=tmp; return; } ``` ---- 接下來你在main跑的時候會發現 ```C++ int main() { int a=6, b=7; sw(a, b); cout << a << b; //67 } ``` 蛤蛤蛤，根本沒有換到 ---- 喔喔，原來是因為我們在$sw()$裡面交換的 只是複製出來的$a$跟$b$而已 真正的本體沒有被交換到!!! 那要怎麼辦呢? 在前面加上&就好 ```C++ void sw(int& a, int& b) ``` ---- 不過在使用引用時，有些事要注意 - 引用必須要有初始值，不能像變數一樣沒有 - 引用的對象必須是變數 (Lvalue) ```C++ int main() { int &x; // CE int &y = 67; // CE int v = 87; int& rv = v; //OK } ``` --- ## 接下來我們看這題 [T27超帥社長出的題目](https://toj.tfcis.org/oj/pro/1021/) ---- 我們會發現 如果單純的這樣寫: ```C++ int f(int x) { if(x==0) return 0; if(x==1) return 1; if(x==2) return 3; if(x==3) return 5; else return q(x-1)+q(x-2); } int q(int x) { return f(x-1)-f(x-2); } ``` ---- WTF，編譯器怎麼在鬼叫 ```txt c:\Users\DB091\Documents\coding\c++\examples\test2.cpp: In function 'int f(int)': c:\Users\DB091\Documents\coding\c++\examples\test2.cpp:12:17: error: 'q' was not declared in this scope 12 | else return q(x-1)+q(x-2); | ^ ``` ---- 喔喔 原來是編譯器不知道 $q()$ 這個函式  ---- 於是我們可以先宣告這個函式之後再補上內容:D ```C++ int q(int x);//先跟編譯器說有這個函式 int f(int x) { if(x==0) return 0; if(x==1) return 1; if(x==2) return 3; if(x==3) return 5; else return q(x-1)+q(x-2); } int q(int x) { return f(x-1)-f(x-2); } ``` --- # 遞迴 (Recursion) ---- 什麼是遞迴? 自己呼叫自己  ---- 遞迴的關鍵就是把大問題拆成小的 一直拆到小到可以馬上算出來or能足夠快算出來 ---- 舉個最簡單的例子: 計算 $n!$ ```C++ int fact(int n) { if (n==1) return 1; // 我們都知道1!==1 return n * fact(n-1); } ``` ---- 因此我們在呼叫 $fact(3)$ 的時候其實是在做: ```txt fact(3) = 3 * fact(2) = 3 * (2 * fact(1)) = 3 * 2 * 1 = 6 ``` ---- 注意此時 return 必須等運算式計算完得出一個實際數值，才能將其作為函數結果傳回。 因此在 $fact(3)$ 中 要先等 $fact(2)$ 計算完畢才能繼續 ---- 如果不加這一行會怎麼樣? ```C++ if (n==1) return 1; ``` 這樣的話 會一直遞迴下去 直到stack overflow造成RE 在寫遞迴的時候一定要看清楚有沒有寫好終止條件! --- 各位知道費式數列嗎 $1, 1, 2, 3, 5, 8, 13 \ldots$ 我們也可以用遞迴求出第$n$項! ```C++ int f(int n) { if(n<=2) return 1; return f(n-1)+f(n-2); } ``` ---- 等一下...怎麼那麼慢... 我們來計算一下f(10)下每個函數會被叫幾次 ----  ---- 發現那麼慢的原因就是因為重複計算太多次相同的東西了! 因此我們可以把遞迴的結果存起來 以後就不用再呼叫了 直接拿出來用 我們把這個加速方法叫做記憶化(Memoization) ---- ```C++ int result[1000005]; int f(int n) { if(result[n]!=0) // 已經被算過了 { return result[n]; } if(n<=2) return 1; return result[n]=f(n-1)+f(n-2); } ``` --- 練習題: [f91](https://zerojudge.tw/ShowProblem?problemid=c002) [河內塔](https://zerojudge.tw/ShowProblem?problemid=a227) [Apple Division](https://cses.fi/problemset/task/1623/) [八皇后問題](https://toj.tfcis.org/oj/pro/657/)