# C++ Function --- #### main is a function * 妳可以認為，當你在執行程式時，作業系統直接call main function來執行程式。 * main 就是你最開始接觸到的function ``` cpp int main(int argc, char** argv) { // context } ``` --- #### What is function * 一連串的執行指令 * 對使用者來說，我只需要知道我要給他甚麼輸入並且知道他會做甚麼事情。 * 不需要知道所有的細節 *  --- #### Use Math as an example * 如何取得直角三角形的斜邊 *  ``` cpp double calculateHypotenuse(double a, double b) { return sqrt(a*a+b*b); } ``` --- #### Why do we need functions * 通通寫在main function內好嗎? --- #### Why do we need functions * 通通寫在main function內好嗎? * 不好? 為什麼? 1. Code reuseable 2. Readability 3. Cooperation --- #### Example * 你能快速地知道這段code在幹嘛嗎  --- #### Example * 那這樣呢 * 從main開始閱讀  --- #### Example * 他們差在哪  --- #### Example * 我們獲得了甚麼 1. Code reuseable * `calculate_gcd` is reused. 2. Readability * We know `a==0` print the gcd and others print the lcm. 3. Cooperation * Engineer A maintains gcd, and Engineer B maintains lcm. --- #### Expression * return_type: 此函數的回傳型態，當你執行完會得到的東西 * function_name: 函數的名稱 * parameters: 此函數的輸入 * context: 如何處理你的input並得到回傳值 * return: 當回傳型態不為void時 則必須寫return ``` cpp return_type function_name(parameters) { // execution context return ...; // 假如return-type不是void時 必須return; } ``` --- #### Example - calculate_gcd * return_type: 回傳一個integer * function_name: 名稱很明確，我要計算最大公因數 * parameters: 兩個型態為integer的參數，在function內代號為x,y * context: 使用while loop來計算gcd * return: 將得到的gcd返回 ``` cpp int calculate_gcd(int x, int y) { int temp; while(y != 0) { temp=x % y; x=y; y=temp; } return x; } ``` --- #### What does Machine do when calling function  --- #### Use stack when register is lack  --- #### Local Variable * 所有定義在function內的變數都是Local Variable * 請問average的a,b,avg跟main中的a,b,avg有甚麼關係嗎? * average的a,b,avg屬於average這個function的local variable * 反之main中的a,b,avg也是如此  --- #### Local Variable * 會在進入function的時候分配記憶體給他們，並在離開function時釋放記憶體 * 進入average後，系統會分配綠色框框中的三個位置給average的a,b,avg使用，並移動stack pointer至下方位置。 * average執行完以後，綠色框框中的位置被釋放，stack pointer被往上移動  --- #### Call by Value & Call by Reference * In C language, always use **Call by Value** * 傳送是用複製的方式傳值，修改不會改到原本的變數 * C++ add **Call by Reference** feature. * 傳送是用別名的方式傳送，修改會改到原本的變數 * Keyword: & in parameters * example: `void fun(int& a);` * 請問會印出甚麼東西來?  --- #### Two way to define function 1. declare and define together ``` cpp int average(int a,int b) { return (a+b)/2; } int main() { int a = average(1,2); } ``` 2. declare first and define later ``` cpp int average(int a, int b); int main() { int a = average(1,2); } int average(int a,int b) { return (a+b)/2; } ``` --- #### Pass the array in the parameters * 1D array: 你可以選擇要不要指定array的長度，如果不指定長度的話會有風險。 ``` cpp void fun(int a[], int b[3]); ``` * multi-dimention array: 只允許第一個中括號內留空格 ``` cpp void fun(int a[1][2]); // ok void fun(int a[][2]); // ok void fun(int a[1][]); // compile error void fun(int a[][]); // compile error ``` --- #### Pass the array in the parameters * Special case * Array is **copied by value**, but modify will affect the original array. * 理由是因為我們複製的東西是**指標**而不是整個array，細節會在之後的章節講到。  --- #### Recursion * The function call its self recursively. * Loop <==> Recursion * Loop 跟 Recursion 理論上是可以互換的 * Recursion的缺點 * 遞迴太多層的話stack會不夠用而導致程式終止 * call function本身會有一定的性能損失(MIPS的jmp指令) --- #### Recursion * 既然這樣為何我們還要用遞迴呢 * 適用於Dynamic Programming以及Divide and conquer的思考邏輯 * 都是將問題拆解成小問題以後，先解出小問題再來煩惱大問題 ``` cpp int factorial(n) { if (n==1) { return n; } else { return factorial(n-1) * n; } } int main() { std::cout<<"5! = "<<factorial(5)<<"\n"; // 5! = 120 } ``` --- #### Recursion * 那要怎麼寫一個recursion呢 1. 將問題分解好 * 我們要計算n! 只需要將n * (n-1)! 即可 2. 一個正確的終止條件，防止無限loop下去 * 當n足夠小而我們已經確定已知解答的時候，就可以設他為中止條件 * n=1的時候 1!=1是大家都知道的 ``` cpp int factorial(n) { if (n==1) { return n; } else { return factorial(n-1) * n; } } ``` --- #### Practice * Sum of two prime * input: a integer * output: print all the solution * Example:  * Compiler Explorer: [Link](https://godbolt.org/z/8KKWKhrdP) * ANS: [Link](https://godbolt.org/z/ec4ae51r1) * 請使用一個function去判斷是否為質數 --- #### Practice 2 - Recursion * 請使用recursion寫出輾轉相除法得到兩個數的最大公因數 * 分解問題: a=18, b=14 輾轉一次後變成 a=14, b=4(18%14)，(18,14) 跟 (14,4)的解答是一樣的 * 終止條件: 當b變成0的時候 --- #### Practice 2 - Recursion * 請使用recursion寫出輾轉相除法得到兩個數的最大公因數 * 請完成gcd這個function  * 如果成功的話會印出  * 如果失敗的話會印出  * [連結](https://godbolt.org/z/qj1PGoTe9) * [ANS](https://godbolt.org/z/c8cb6GMcP)