昨天講了 Algorithm 的定義和 5 大標準，今天就來碰點程式，來講講遞迴吧！

甚麼是遞迴？

遞迴（recursion）指的是：演算法或程式中，含有自我呼叫（self-calling）的敘述
這表示函式會自己呼叫自己
來看個例子：

int multiply(int x, int t){
    if(t == 0) return 0;
    return x + multiply(x, t - 1);
}

你會發現 multiply 函式中，呼叫了 multiply 自己，這就是遞迴。

一個遞迴函式包含甚麼呢？

有三個部分：

1. 終止條件：遞迴一定要可以停下來，不然程式就會像永動機一樣一直遞迴遞迴遞迴，直到 Stack Overflow 為止（關於Stack的部份我們晚一點說）
2. 遞迴項：也就是 self-calling 的 statement
3. 狀態的變動：每次的 self-calling 的參數要有所變化，使得條件越來越接近終止條件，遞迴才能成功終止

看個錯誤示範：

void printStar(int times){
    if(times == 0) return;
    else{
        cout << "*";
        printStar(times);
    }
}

可以看到當印完一個星號之後，遞迴項一樣是 times，那等於 times 永遠沒有機會到達 0 次（終止條件）
所以，這個遞迴除了手動 terminate，是不會停下來的。
正確示範：

void printStar(int times){
    if(times == 0) return;
    else{
        cout << "*";
        printStar(times - 1);
    }
}

遞迴 v.s. 非遞迴

除了遞迴之外，還有一種能夠重複執行動作的結構，也就是 loop：迴圈
通常會稱之 Non-recursion 或 itertion
在這個世界上，必定存在 recursive 和 non-recursive 的 solution
如果你的腦子中，先想到的是遞迴解，那恭喜你，可以透過 SOP 把非遞迴解求出
但如果你是先想到非遞迴解，那要找出遞迴解就只能靠靈感了，可能要被雷打到或是踢到小指
那它們有甚麼差別呢？
1. 遞迴程式碼較精簡且容易解釋，非遞迴較複雜
以階乘為例：
Recursive Function:

int fac(int N){
    if(N == 0) return 1;
    else return N * fac(N - 1);
}

這個程式碼簡單明瞭，簡直是把數學定義直接寫出來：
0! = 1；N! = N * (N - 1)!

Iterative Function:

int fac(int N){
    int total = 1;
    for(int i = 1; i <= N; i++){
        total *= i;
    }
    return total;
}

雖然有學過程式的人可能還是很簡單，但沒學過的人可能已經開始看不懂了。
就算要解釋，也要解釋 for 迴圈運作，每次乘 i 並加入 total，最後再回傳 total。
相較之下，遞迴函式的表達問題的能力比較強，且比較不複雜。
2. 遞迴 Debug 較困難，非遞迴 Debug 較容易
可以從第一點看出來，當遞迴函式出錯時，程式碼中幾乎沒有呈現甚麼有用的資訊給 programmer，programmer就要自己去追蹤每次遞迴，看看錯誤在哪
反觀非遞迴提供許多程式實作的步驟和邏輯，programmer 就比較好 Debug 了。
3. 遞迴需要 Stack 支援：
當遞迴被呼叫時，系統會將參數（parameter）、區域變數（local variable）以及返回位址（return address）push 進堆疊，這三個部份合稱Activation Record。
當函數執行到 end(}) 敘述時，系統會開始 pop 堆疊的 Activation code，並根據上面的資料進行操作。
但也就是因為 recursive function 需要這些額外的 Stack 操作，以及大量的函式呼叫，因此
Recursive 的程式效率會比 iterative 來的更差

用個表總結一下

明天繼續說遞迴的經典題目：Fibonacci Series & Hanoi Tower