**函數 Function** --- 數學課學的函數 $$f(x) = x^2 + 3x + 2$$ $f(1) = 6$ $f(6) = 56$ ---- 在程式裡的函數概念與數學差不多 丟東西給函數，函數會回傳結果 --- 函數需要的東西 - 函數名稱 - 函數定義 - 若干個參數（arguments） - 一個回傳值（return value） ----  ---- 寫法一 ```cpp= #include<bits/stdc++.h> using namespace std; int dfs(int now,int target); int main(){ dfs(0,5); return 0; } int dfs(int now,int target){ //something here } ``` ---- 寫法一 ```cpp= #include<bits/stdc++.h> using namespace std; int dfs(int now,int target){ //something here } int main(){ dfs(0,5); return 0; } ``` --- 回傳值可以是各種資料型態 ex. `double float vector<int> pair<int,int>` 甚至是自己寫的struct 特殊形態`void` 沒有回傳值 `return;` ---- `return` 可以回傳資料，且停止程式 ```cpp int main(){ return 0; } ``` --- 變數的生命週期 ---- 變數就像是一個工具，紀錄著value 但工具總有一天會損壞或是腐朽 變數也一樣 ---- 最基礎： 全域變數 VS 區域變數 刑法 VS 地方自治條例 每個地方都能適用刑法 但台北市不能適用基隆的地方自治條例 ---- ```cpp= #include<bits/stdc++.h> using namespace std; int n;//全域變數 int main(){ int c = 0;//區域變數 return 0; } ``` ```cpp= #include<bits/stdc++.h> using namespace std; int n = 5; int func(int n){ int ans; ans = n*n;//同名以最晚宣告之變數為主 return ans; } int main(){ cout<<ans;//error cout<<n;//correct cout<<func(4); return 0; } ``` ---- 傳入陣列時只能傳1維 高維度也能傳，但需要別的寫法(指標 之後會教) 打競程時最好的方法就是在全域宣告陣列 這樣可以直接用 ```cpp= #include<bits/stdc++.h> using namespace std; int arr[]={1,2,4,5}; int func(int arr[],int size_t){ //something here } ``` --- 大魔王 遞迴、遞歸 ---- 一句話介紹：自己呼叫自己 ---- 數學上也有遞迴，不過跟程式的概念不太一樣 ---- 定義一函數 $f(x) = f(x-1) + f(x-2) 且f(1) = 2,f(2) = 3$ 如果我們想知道$f(7)$的值，就必須知道$f(6)以及f(5)$ 以此類推 ---- 程式碼 ```cpp= int f(int x){ if(x==1) return 2; if(x==2) return 3; return f(x-1) + f(x-2); } //這裡有個優化方法，可以想想看 ``` ---- 由此可知，遞迴的特性為 **把一個大題目切成很多個小題目** --- 遞迴經典題目：河內塔 ---- [去玩](https://www.mathsisfun.com/games/towerofhanoi.html) ---- 公式 $2^n-1$ and [題目](https://zerojudge.tw/ShowProblem?problemid=a227) ---- 由前幾頁提到的遞迴特性可知 我們能把第$n$個搬去C，而$n-1$個搬去B ---- 遞迴比較吃理解，但也是程式中重要的東西 --- 優化：記憶遞迴 ---- 如果一個程式要計算很多次$f(x)$的值 那不斷地計算相同事物就會浪費時間 ---- ```cpp= int mem[Mxn]; int f(int x){ if(x==1) return 2; if(x==2) return 3; if(mem[x]!=-1) return mem[x]; mem[x] = f(x-1) + f(x-2); } ```