<H1>
單元一 遞迴
</H1>

:::success
原理 : 在function裡面**有條件**的呼叫自己。
目的 : 把一個問題拆解成許多小問題，減少寫程式的負擔。
:::

舉例:
Factorial, GCD, Binary Search, Tower of Hanoi...

:::info
遞迴四大點:
1.把問題拆解成更小的問題
2.看遞迴的時候有沒有減少問題大小
3.看有沒有Base Case，若沒有，可能會造成**無窮迴圈**
4.所有的Case最後都會到Base Case。
:::
以下是以遞迴實作GCD的程式碼

int gcd(int x, int y){
    if(x<y) gcd(y,x);
    if(!x%y) return y;
    else return gcd(y,x%y);
}

以下是用遞迴實作Merge Sort的程式碼

void merge(vector<int>&v, int front, int middle, int end){
    vector<int> temp;
    int i,j;
    i = front;
    j = middle+1;
    while(i<=middle && j<=end){
        if(v[i]<=v[j]){
            temp.push_back(v[i]);
            i++;
        }
        else {
            temp.push_back(v[j]);
            j++;
        }
    }
    
    while(i<=middle){
        temp.push_back(v[i]);
        i++;
    }
    
    while(j<=end){
        temp.push_back(v[j]);
        j++;
    }
    
    for(i = front ; i <= end ; i++){
        v[i] = temp[i-front];
    }
    
}

void mergeSort(vector<int>&v, int front, int end ){
    if(front>=end) return;
    int middle = (front+end)/2;
    mergeSort(v,front,middle);
    mergeSort(v,middle+1,end);
    merge(v,front,middle,end);
}

:::warning
遞迴缺點 : 會占用較多記憶體空間和 花費較多的CPU時間。
:::

## 河內塔問題

:::info
有三根杆子A，B，C。A杆上有 N 個 (N>1) 穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至 C 杆：
1.每次只能移動一個圓盤。
2.大盤不能疊在小盤上面。
:::

以下是神秘的程式碼:

void Towers(int n, char source, char dest, char spare ){
    if(n==1){
        printf("Move top disk from %c to %c", source, dest);
    }
    
    else{
        Towers(count-1,source,spare,dest);
        Towers(1,source,dest,spare);
        Towers(count-1,spare,dest,source);
    }
}

時間複雜度: O(2^n)