<style>

html, body, .ui-content {
background-color: #333;
color: #ddd;
}

body > .ui-infobar {
display: none;
}

.ui-view-area > .ui-infobar {
display: block;
}

.markdown-body h1{
color: #9CCEF2;
}
.markdown-body h2{
color: #B1D6CA;
}
.markdown-body h3{
color: #F5F6B6;
}
.markdown-body h4,
.markdown-body h5,
.markdown-body h6 {
color: #ddd;
}

.markdown-body h1,
.markdown-body h2 {
border-bottom-color: #ffffff69;
}

.markdown-body h1 .octicon-link,
.markdown-body h2 .octicon-link,
.markdown-body h3 .octicon-link,
.markdown-body h4 .octicon-link,
.markdown-body h5 .octicon-link,
.markdown-body h6 .octicon-link {
color: #fff;
}

.markdown-body img {
background-color: transparent;
}

.ui-toc-dropdown .nav>.active:focus>a, .ui-toc-dropdown .nav>.active:hover>a, .ui-toc-dropdown .nav>.active>a {
color: white;
border-left: 2px solid white;
}

.expand-toggle:hover,
.expand-toggle:focus,
.back-to-top:hover,
.back-to-top:focus,
.go-to-bottom:hover,
.go-to-bottom:focus {
color: white;
}

.ui-toc-dropdown {
background-color: #333;
}

.ui-toc-label.btn {
background-color: #191919;
color: white;
}

.ui-toc-dropdown .nav>li>a:focus,
.ui-toc-dropdown .nav>li>a:hover {
color: white;
border-left: 1px solid white;
}

.markdown-body blockquote {
color: #bcbcbc;
}

.markdown-body table tr {
background-color: #5f5f5f;
}

.markdown-body table tr:nth-child(2n) {
background-color: #4f4f4f;
}

.markdown-body code,
.markdown-body tt {
color: #eee;
background-color: rgba(230, 230, 230, 0.36);
}

a,
.open-files-container li.selected a {
color: #5EB7E0;
}

</style>

###### tags: `tgirc早修book`

# 經典遞迴題型

本篇整理了幾種遞迴的經典題型。

## 最大公因數

最大公因數通常是利用 [輾轉相除法](https://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95) 的方式來實作。每次讓 a 與 b 兩者交替互相取餘數。
以下是 Top-down 的作法。

int GCD(int a, int b){
    if(b == 0){
        return a;
    }
    
    return GCD(b, a%b);
}

Bottom-up的作法則是如下：

while(b != 0){
    int temp = a;
    a = b;
    b = temp % a;
}

cout << a;

## 費波納契數列

費波納契數列，又稱費式數列。
該數列第零項為 0，第一、二項為 1，之後每一項都是其前兩項的和，也就是如下：

f(n) = 1                (n = 1 or 2)
f(n) = f(n-1) + f(n-2)  (n > 2)

Top-down 的作法如下：

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

Bottom-up的作法則是如下，一般會建立一個陣列來儲存所有值：

int arr[n];
arr[0]=0;
arr[1]=1; arr[2]=1;

for(int i=3; i<n; i++){
    arr[n] = arr[n-1] + arr[n-2];
}

cout << arr[n];

## 字元排列組合

若有 n 個字元，輸出其所有排列方式。

假設今天的字元有 a, b, c 三個，把它的所有排列方式表示為 (a, b, c)，那它的所有排列方式就是：

(a,b,c) = [a + (b,c)] + [b + (a,c)] + [a + (b,c)]

也就是說，讓所有字元各擔任一次字串開頭，後面接剩下的字元的所有排列方式，而剩下的字元的所有排列方式又可用相同方式處理。

直到剩下一個字元時，單一個字元的排列方式只有一種，此時即可停止。

string str;

void Perm(int i, int n){
    if(i == n){
        cout << str << "\n";
    }
    else{
        for(int j=i; j<n; j++){
            swap(str[i], str[j]); //把j字元換到開頭
            Perm(i+1, n);         //剩下的字元作排列組合
            swap(str[i], str[j]); //把j字元放回原位
        }
    }
}

## 河內塔

河內塔是一個大盤子在下，小盤子在上，總共三根柱子可以放盤子的裝置。
目標是將 A 柱子上的所有盤子按照順序移到 C 柱子上，一次只能移一個盤子，且大盤子不能放在小盤子上，按照順序輸出移動步驟。

首先觀察只有 2 個盤子的情況，先將小盤子由 A 移到 B，再把大盤子由 B 移到 C ，最後把小盤子由 B 移到 C。

其實可以想成是把最大的盤子以上的小盤子全部移到 B 柱子上，再把最底下的移到 C 柱子，最後把 B 柱子的盤子全部移到 C 柱子上。

此時我們把 A 稱為起始柱，B 為中間柱作為轉運站，C 則是終點柱。所有的 n 層塔都可拆為以下步驟：

1. 將 起始柱 上 n-1 個盤子移到 中間柱
2. 將 起始柱 最底下剩餘的 1 個盤子移到 終點柱
3. 將 中間柱 上 n-1 個盤子移到 終點柱

而 n-1 個盤子的移動方式，又可按照這個步驟執行下去。
移動至剩下一個盤子時，就只需將那個盤子直接由起點柱移到終點柱。

:::spoiler <font color="F5F6B6">**流程圖**</font>








:::
>

void Hanoi(int n, char A, char B, char C){
    //把n個盤子由A柱子移至C柱子
    //A為起點柱，B為中間柱，C為終點柱
    
    if( n==1 ){
        cout << A << " -> " << C;
    }
    //如果只有一個盤子，就直接由起點柱移到終點柱
    
    else{
        Hanoi(n-1, A, C, B);
        //將n-1個盤子由起點柱移到中間柱
        Hanoi(1, A, B, C);
        //將最底下的1個盤子由起點柱移到終點柱
        Hanoi(n-1, B, A, C);
        //將n-1個盤子由中間柱移到終點柱
    }
}