# [資料結構] CH1. Algorithms Recursions

## 演算法(Algorithm)
* 定義：一個用來完成某種目的的程序，且擁有以下五點性質：
1. 輸入(Input)：可以有零個或零個以上的輸入。
2. 輸出(Output)：有**至少一個**的輸出。
3. 明確性(Definiteness)：每個步驟都要清楚且有意義。
4. 有限性(Finitense)：如果我們逐步執行這段演算法，它一定會在有限的步數內完成/結束。
5. 有效性(Effectiveness)：每個步驟都得是合理，且可被執行的。

* 程式(program)和演算法的差別，在於程式不具**有限性**。

## 遞迴(Recursive Algorithms)
* 遞迴是相當好用且強大的演算法，它可以將一些複雜的程序簡單地表達出來。
* 遞迴可以簡單分為三類：
1. 直接遞迴(Direct Recursion)：
一個Function在結束前call自己。
2. 間接遞迴(Indirect Recursion)：
A Function在結束前call了B Function，且B Function又call回A。
3. 尾端遞迴(Tail Recursion)：
一個Function在最後call自己；這屬於直接遞迴的一種特例。
* 遞迴與非遞迴的比較：

| 遞迴 | 非遞迴 |
| -------- | -------- |
| 程式碼簡單且乾淨|程式碼複雜且凌亂|
|可讀性高|不易理解|
|執行耗時|執行快速|

* 練習1 階層

int factorial(int a)
{
    if(a==0)return 1;
    else return factorial(a-1)*a;
}

* 練習2 費氏數列

int Fibonacci(int a)
{
    if(a==0)return 0;
    else if(a==1)return 1;
    else return Fibonacci(a-1)+Fibonacci(a-2);
}

* 練習3 阿克曼函數

int Ackerman(int m,int n)
{
    if(m==0)return n+1;
    else if(n==0)return Ackerman(m-1,1);
    else return Ackerman(m-1,Ackerman(m,n-1));
}

###### tags: `DS` `note`