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 時)

第一條式子就是邊界條件，這項 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……

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

例二：費氏數列

費氏數列（費波那契數列） -> 相關介紹

費氏數列是一段第 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;
}

兩種實作方式

這裡以階乘為例，示範兩種實作遞迴的方式，Top-down 以及 Bottom-up。

階乘的定義如下：

!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 意即 從第n項開始，一路往回求第1項。

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

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




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

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

Bottom-up

Top-down 是由最後方往回推，而 Bottom-up 則是與之相反。
也就是 從第1項開始，一路向後推至第n項。

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



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

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

tags: tgirc早修book

遞迴