昨天講了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);
   }
   

   根本是直接把數學的定義寫出來，沒學過程式的人也一看就懂：
   N! = N * (N - 1)!, 0! = 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