<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`

# 遞迴

大雄在房裏，用時光電視看著從前的情況。電視畫面中的那個時候，他正在房裏，用時光電視，看著從前的情況。電視畫面中的電視畫面的那個時候，他正在房裏，用時光電視，看著從前的情況……
（無限重複 on）

## 遞迴基本概念

遞迴是一種將大問題拆解成小問題並分項解決的方式。

其適用於各種「可以整理出與前項的關係式」的狀況。
作法大致上是整理成出一個遞迴通式，使其每項都固定與前 n 項有關。

以數學式表達就像這樣：

f(n) = a ‧ f(n-1) + b ‧ f(n-2) + …

每一項都會固定與前幾項有特定關係，這樣整理出來後，要實作遞迴程式就方便的多了

### 例一：1 ~ n 的總和
有一函數 f(x) = 1+2+3+ … +x
求給定 x 值的 f(x)

程式如下：

#include <iostream>
using namespace std;

int f(int x){
    if(x == 1) return 1;
    //如果x=1，那麼f(x)=1
    
    return f(x-1)+x;
    //如果x不是1，那麼 f(x) = f(x-1)+x
    //而 f(x-1) 就是直接將 x-1 作為參數傳入 f()，並回傳 f(x-1) 的值
    //即使是在 f() 內也可以呼叫自己
}

int main(){
    int x;
    cin >> x;
    cout << f(x) << "\n";
    return 0;
}

首先，先觀察前幾項的規律

f(1) = 1
f(2) = 1 + 2            = f(1) + 2
f(3) = 1 + 2 + 3        = f(2) + 3
f(4) = 1 + 2 + 3 + 4    = f(3) + 4
.
.
.

可以觀察到如下規律：

f(x) = 1            (x = 1 時)
f(x) = f(x-1) + x   (x > 1 時)

第一條式子就是<font color="F5F6B6">**邊界條件**</font>，這項 f(x) 沒有前一項，所以需要獨立討論。
而第二條式子就是一般情況下，f(x) 所遵循的規則。

程式實作常用的作法是在函數中呼叫函數本身，並訂定邊界條件。

流程大致上是主程式呼叫 f(x)，而 f(x) 中需要用到 f(x-1)，所以呼叫f(x-1)，但在 f(x-1) 中又會用到 f(x-2)，所以呼叫 f(x-2)……

就這樣一路呼叫到 f(2)=f(1)+2 時，f(1)=1 所以回傳 1。
這時 f(2) 就有了 1+2 = 3 這個值，並將 3 回傳給 f(3) = f(2)+3 = 3+3 = 6，然後是f(4) = f(3)+4 = 6+4 = 10……

大部分的遞迴都可以拆成這樣的步驟來進行。

### 例二：費氏數列
費氏數列（費波那契數列） -> [相關介紹](https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0)

費氏數列是一段第 0 項為 0、第 1 項為 1，之後的項數都由前面兩項相加而成的數列
-> 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , ...

輸入 x，求費氏數列的第 x 項

#include <iostream>
using namespace std;

int f(int x){
    if(x == 0) return 0;
    else if(x == 1) return 1;
    
    return f(x-1) + f(x-2);  //前兩項之和
}

int main(){
    int x;
    cin >> x;
    cout << f(x) << '\n';
    return 0;
}

## 兩種實作方式

這裡以階乘為例，示範兩種實作遞迴的方式，<font color="F5F6B6">Top-down</font> 以及 <font color="F5F6B6">Bottom-up</font>。

階乘的定義如下：

!1 = 1
!2 = 1 ‧ 2
!3 = 1 ‧ 2 ‧ 3
!4 = 1 ‧ 2 ‧ 3 ‧ 4

!n = 1 ‧ 2 ‧ 3 ‧ … ‧ n

輸入 n，求 n 的階乘

### Top-down

Top-down 意即 <font color="F5F6B6">**從第n項開始，一路往回求第1項**</font>。

通常 Top-down 會利用副程式自我呼叫來實作。
剛剛上面提到的兩題，其實就是以 Top-down 的方式完成的。

先寫出一個能解決問題的函數，再以遞迴方式完成

int f(int n){
    if(n == 0) return 1;
    return n * f(n-1);  //由 f(n-1) 往回推
}

:::info
因為系統本身是有限制的，當遞迴過深時會導致 overflow
:::

### Bottom-up

Top-down 是由最後方往回推，而 Bottom-up 則是與之相反。
也就是 <font color="F5F6B6">**從第1項開始，一路向後推至第n項**</font>。

通常 Bottom-up 會利用 for迴圈 搭配陣列或是變數來實作。

for(int i=1;i<=n;i++){
    num[i]=num[i-1]*i;
}

##

相較於 Top-down，Bottom-up 的效率比較好，只有極少數情況才會出錯，並且風險也比較低，所以建議可以多多練習 Bottom-up，但 Top-down 的用法也需學會