章節0-4.C++基礎語法(四)

函式

雖然在C++中要重複執行一樣的程式可以使用迴圈，但如果要重複執行的程式較複雜，可能是要在程式中很多不同位置執行，又或者是每次執行需要稍微調整執行的內容，迴圈就不完全適合了。

此時就可以透過「函式(function)」的宣告來解決，所謂函式就是將一坨執行特定功能的程式碼包在一起以便後續使用，通俗一點就是假如每行程式碼都是可以執行一個特定工作的小零件，函式就是將這些小零件組裝成機器，未來要執行這項工作時可以直接使用機器就好。

而其實函式的宣告在學到這裡之前大家一定都做過了，那就是int main(){...}，其實這個main就是一個函式，在程式開始時會執行main函式的內容。所以知道這件事後再去看函式的宣告就變得簡單許多了，函式宣告在全域的位置，也就是int main()的上方，宣告方式為「回傳型別 函式名稱(參數清單){程式碼}」，如果覺得看上去還是有點複雜，以下一一解釋。

回傳型別部分，就是函式做完後要丟什麼樣的數值回去，或者不丟任何數值回去，通常對應函式要做的事情。
例如今天的函式f是代表數學上的函數f(x)=...，並且計算結果都在int範圍內，那麼就可以宣告int f(...){...}，代表運算完後會丟一個int代表該函式的運算結果；而關於回傳型別，前面說到也可以不丟任何數值回去，那麼就在回傳型別打上void即可。

請注意main函式的型別int是固定的，不能改動，會使程式無法編譯。

int lucky_number(){ //定義函式lucky_number，因為希望最後會丟回一個整數，故型別宣告int
    //計算幸運數字的過程
    //最後丟回幸運數字
}
void say_hello(){ //定義函式say_hello，因為只是執行說你好的動作，做完不需要特別丟回數值，宣告void即可
    cout<<"Hello!\n";
}

函式名稱就如同變數名稱一樣，代表後續要如何呼叫這個函式。

參數清單代表的是需要丟給這個函式哪些變數。
以上面數學函數f(x)=...為例，因為今天f(x)的結果受到x值的影響，或者說x值是該函數中的變數，需要依據其值帶入做運算，所以宣告函式時會需要加入參數int x，也就是要宣告int f(int x){...}。
另外也可以宣告多個參數，假設今天我們有個函式是給他a,b會回傳a+b(雖然沒必要特別宣告這樣的函式)，那麼宣告時就可以寫int add(int a,int b){...}。

int test(int a,long long int b,double c,string d){ //參數可以有許多個，也可以不同型別，宣告時由,分隔，每個參數各自需要型別
    //...
}
void say_hello(string name){ //給此函式一個name參數，就會執行輸出「Hello, (name)!」
    cout<<"Hello, "<<name<<"!\n";
}

至於程式碼部分就是函式要執行的內容了。
值得注意的是在函式中有個「return 回傳值;」的語法，對應到最前面所講的回傳型別，所謂return翻成中文就是回傳，代表把這個函式的運算結果丟回去，但同時因為回傳代表函式運算結束，也會直接終止函式的執行。
需要注意的是若有回傳型別就要記得return，也要注意回傳型別必須與函式宣告的一樣，假如在函式中途有利用if來在某些條件下return，也記得檢查所有情況都能有回傳值，避免程式出現錯誤。
而void函式，也就是無回傳值的函式，一樣可以使用return，只不過只寫成「return;」，作用通常為中途終止函式執行。

請注意main函式一樣可以return來中止執行，但需要注意只能寫「return 0;」，其他回傳值會視為程式意外中斷，且執行「return 0;」後整個程式會立即結束。

bool is_prime(int n){ //判斷參數n是否是質數的函式
    for(int i=2;i<n;i++){ //透過查找2~n-1是否有n的因數來判斷質數，若除了1、n外無因數就是質數
        if(n%i==0)return 0; //只要執行到n被i整除就可以回傳0，立即終止函式
    }
    return 1; //但若到最後都沒有2~n-1的函式，便可回傳1
}

了解如何完整的宣告函式後，就可以使用函式了，使用的方式就是在程式碼中寫上「函式名稱(引數清單);」，此處引數清單是對應宣告時的參數清單，假設宣告的函式為void test(string s,int n)，有兩個參數分別為字串s與整數n，假如要以s="Samuel"、n=5執行test中的程式碼時，就寫test("Samuel",5)，也可以將main函式中的變數以這樣的方式傳給其他函式。

#include<bits/stdc++.h>
using namespace std;
int pow(int base,int exponent){ //宣告函式來處理指數，計算base的exponent次方
    int result=1; //此為最終要回傳的變數，因為任何正整數的0次都是1，故初始化為1
    for(int i=0;i<exponent;i++)result*=base;
    return result;
}
int main(){
    int x,y;
    cin>>x>>y;
    cout<<pow(x,y); //因回傳型別為int，故使用此函式時等同使用int，當函式運算完後會將結果丟至這裡
    //此程式輸入「x y」後，會輸出「x的y次方」(結果範圍超出int會因溢位而錯誤)
}

重點整理:全域變數、區域變數概念
從0-1就陸續有提到全域、區域的概念。

全域(global)就是宣告在main上方位置的變數，整個程式包括main函式以外的函式都可以使用，並且值是共通的，也就是說宣告了一個全域變數int n後，在main中將其設為10後，在另一個函式使用n就會是10。
另外關於全域變數的宣告還有一個重點，就是雖然全域變數在不同函式都可以使用，但由於C++的執行順序還是由上而下，因此若宣告了一個函式使用全域變數n後才在下面宣告全域變數n，會導致編譯失敗，因此建議全域變數一律宣告在所有函式前。

區域(local)則是宣告在一個區塊中的變數，所謂區塊可以理解為一個{}，在那個{}裡宣告的變數就只在那個{}裡可以用。
如main函式中宣告int n就只能在main中使用，若在其他函式中使用則會跑出「該範圍內找不到n」的編譯錯誤，假使此時在其他函式中宣告了另一個int n，那麼兩個n也是代表不同的變數。
除此之外在for、while迴圈或if-else後的{}宣告的變數同理，在{}外就不能使用，for(int i=0;;)中的i亦同，只能在for迴圈內的範圍使用。
如此來看各個函式的參數，也是同樣概念，只有在該函數可以用。

在這邊進行一個小結，就是宣告變數究竟選擇全域還是區域好呢，個人的建議是除了陣列一律宣告在全域外，其他變數依據需求，假設不同函式都會使用到，那麼就宣告在全域，否則宣告在區域就好了。

那假設一樣的變數名稱同時在全域跟區域都有宣告呢？
先聲明請在實作時避免此種請況，以免產生bug造成自己困擾。但假如題目出現此種情況，或疏忽發生在了實作的程式碼，那麼會有以下現象，每個宣告完的變數都是不同的變數，而當使用該變數時，會取最裡面或者說最靠近的變數，如以下例子。

#include<bits/stdc++.h>
using namespace std;
int n=1;
int main(){
    int n=2;
    for(int i=0;i<2;i++){
        int n=3;
        cout<<n<<'\n'; //這邊會輸出3，因為此時最裡面的或者說最靠近的是n=3的n
    }
    cout<<n; //這邊會輸出2，因為已經在for迴圈外所以並不會受裡面的int n=3;影響，此時最內圈或者說最靠近的是n=2的n
}

遞迴

遞迴(recursion)是一種在程式設計中用來解決問題的方法，特點是函式會呼叫自己。這個概念聽起來可能有點抽象，但我們可以用一些簡單的例子來幫助理解。

我們以利用遞迴來實作階乘舉例，所謂的n階乘(寫作n!)就是從1乘到n的結果，並特別定義0!=1。
因此我們也可以用下方式定義：「若n=0，則n!=1，否則n!=n*(n-1)!」，可以發現由此定義，1!=1*0!=1*1=1。2!=2*1!=2*1=2，3!=3*2!=3*2=6，4!=4*3!=4*6=24，以此類推，與直接定義成1乘到n的結果一樣，但我們另外定義的這種方法其實就是遞迴的概念了。

遞迴的函式基本上需要能處理以下兩種情況。
基礎情況(Base Case，我也喜歡稱其為終止情況)：這是遞迴結束的條件。如果沒有基礎情況，遞迴函式會無限呼叫自己，導致程式崩潰。以上述階乘的例子，「若n=0，則n!=1」就是基礎情況。
遞迴情況(Recursive Case)：在這種情況下，函式會呼叫自己。以上述階乘的例子，「否則n!=n*(n-1)!」就是遞迴情況。

因此將上述的內容轉換成程式，會如下，能正確算出n!(當然前提是不發生溢位的情況)。

int factorial(int n){ //階乘的英文為factorial，以factorial(n)代表n!
    if(n==0)return 1;
    else return n*factorial(n-1);
}

稍微描述一下其詳細計算過程，這在APCS部分觀念題中是重要概念。
假設今天要計算factorial(3)，此時函式運行會return 3*factorial(2);，但因為電腦沒辦法直接知道其結果，因此暫時不會回傳，會先計算factorial(2)，然後會經過一樣的事情直到呼叫factorial(0)，然後因為factorial(0)會觸發基礎情況，直接回傳1，因此就可以解決factorial(1)的結果，然後再依序解決factorial(2)、factorial(3)。

還有另一個常見的例子是計算費氏數列，考慮費氏數列之定義，第一項、第二項為1，而後的每一項會是前兩項的和，以遞迴定義則是以f(n)代表費氏數列第n項有「若n=1或n=2，則f(n)=1，否則f(n)=f(n-1)+f(n-2)」。

int f(int n){
    if(n==1||n==2)return 1;
    else return f(n-1)+f(n-2);
}

其實這個例子雖然常見但並不好，效率奇差，計算時間隨n變大成指數級增長，計算第50項就需要數天時間，但結果是正確的。
之所以選擇這個例子是希望讀者能思考幾個問題，一是假如基礎條件只設n==1會怎樣，答案在右下方，點擊可以展開；第二個問題是，為何效率會不佳，透過模擬其運算過程應該就能略知一二，詳細討論就不寫在這裡了，會與1-1、3-1兩個章節有關，慢慢學下去就好了。

遞迴pro

其實前述兩個例子都不好，因為仔細想一下就可以發現只要單純開個陣列，再利用for迴圈由小算到大就行。
只不過由於多數教學都習慣利用這兩個例子進行舉例，也確實這兩個例子有其好理解的優點，因此仍然保留這兩個例子。

但我認為這兩個例子容易讓初學者搞不懂為何要有遞迴，以及遞迴的使用時機，因此在此提出不同的例子與理解方法。
遞迴的核心概念是，將程式遇到的問題，以「由大拆解為小」的方式計算；但前述兩個例子的性質都是，以「由小組合成大」會更好理解的。

而什麼是「由大拆解為小」呢？假設今天有題目是要輸入「1」時輸出「1」，輸入「2」時輸出「1 2 1」，輸入「3」時輸出「1 2 1 3 1 2 1」，以此類推，而規則講白了就是標準的遞迴，1是基礎情況，大於1的n要輸出「(n-1)的內容 n (n-1)的內容」。因此可以用以下方式快速實作。

void f(int n){
    if(n==1){ //基礎情況
        cout<<1<<' ';
        return; //提早結束，若是基礎情況便不再執行後續的遞迴情況
    }
    //以下都是遞迴情況
    f(n-1);
    cout<<n<<' ';
    f(n-1);
}

當然除了遞迴還有其他方法解決以上問題，但遞迴是相對好實作的。
希望利用以上例子能幫讀者更好體會遞迴的用處。如果仍對遞迴不太了解也沒關係，如果是選擇題可以模擬遞迴過程，並觀察規律、找出遞迴的意義，而若是實作題的話，需要使用到較多遞迴的題目會需要搭配其他概念，後續最快用到較多遞迴的章節為3-3。