Skip to main content

1.1 數學中的遞迴 vs 程式中的遞迴

數學中的遞迴

在高一數學課時，學習到使用遞迴解決數學上的問題，以下幾個是簡單的範例

  1. 小朋友上樓梯：有一位小朋友要走樓梯上樓，他一次可以往上走一階或一次走兩階，問你若要走 $n$ 階，共有幾種走法?

    • 在此我們可以藉由上一階、上兩階的特性，將問題轉換成，若我要走到第 $i$ 階，則他必是從 $i - 1$ 和 $i - 2$ 階走過來的，下一步，就可以列成遞迴關係式

    \[F(x)= \begin {cases} F(x-1)+F(x-2) & \text{if }x>1 \\ 1 & \text{if } x = 1 \\ 2 & \text{if } x = 2\end{cases}\]

  2. 遞迴轉換：請將一個等差數列 $F(x)=3x+5$ 轉換成遞迴關係式

    • 很容易的第一項需要特別定義 $F(0)$，接下來的這一項就會式上一項再加3，列成關係式 \[F(x)= \begin {cases} F(x-1)+3 & \text{if }x>0 \\ 5 & \text{if }x=0\end{cases}\]

典型利用遞迴來找到解決問題的方法

  • 當遇到一個不易解決的問題時，試著找出分割這個問題的模式(建立遞迴關係式)
  • 找到之後藉由分割來將這個問題不斷地縮小
  • 當問題縮小到一定的大小時，我們可以直接解決該問題(決定終止條件)
  • 最後合併各個已解決小問題的答案即得到原問題的答案。(設計遞迴函式)

程式中的遞迴

　　在上面的一些例子中，都是使用學過的數學遞迴來解決一些數學上的問題，若是請你將上述問題變成程式問題，作法跟數學一模一樣，可以想像成$F(x)$就是程式當中的呼叫函數，換句話說，只需要藉由呼叫同一個函數的前幾項，就可以找到答案。接下來我們將上面兩個問題轉換成程式

  1. Ex101小朋友上樓梯

    • 題目連結
    • 在此題中，唯一需要做的事就是將函數的回傳值設定為$F(x)=F(x-1)+F(x-2)$，再去注意中止條件即可
    • 程式碼
    #include<iostream>
using namespace std;
int f(int n)
{
    if(n <= 2) return n;
    return f(n - 1) + f(n - 2);
}
int main()
{
    int n;
    cin >> n;
    int ans = f(n);
    cout << ans << endl;
    return 0;
}

  2. Ex102遞迴轉換

    • 題目連結
    • 這題只需要將定義好的遞迴關西式帶入即可，同時也須注意中止條件
    • 程式碼
    #include<iostream>
using namespace std;
int f(int x)
{
    if(x == 0) return 5;
    return f(x - 1) + 3;
}
int main()
{
    int n;
    cin >> n;
    int ans = f(n);
    cout << ans << endl;
    return 0;
}

  3. Ex103階層(此題為額外題目，上述並未提及)

    • 題目連結
    • 題目敘述：給定一個數字$n$請求出$n!$的答案
    • 定義遞迴關係式$f(x)=n\times f(x-1)$
    • 決定中止條件$f(0)=1$
    • 設計遞迴函式\[f(x)= \begin {cases} f(x)=n\times f(x-1) & \text{if }x>0 \\ 1 & \text{if }x=0\end{cases}\]
    • 程式碼
    #include<iostream>
using namespace std;
int f(int x)
{
    if(x == 1) return 1;
    return f(x - 1) * x;
}
int main()
{
    int n;
    cin >> n;
    int ans = f(n);
    cout << ans << endl;
    return 0;
}

相信你已經學會了如何藉由遞迴關係式來解決問題，以下為練習題

練習題

以下題目請使用遞迴來完成，藉此來練習設計遞迴的技巧

  1. P101階層(進階版)
    • 題目連結
    • 題目敘述：給定兩個數字$a, b$保證此兩數字都是偶數，問$a\times (a + 2)\times (a + 4)\times ...\times (b - 2)\times b$的答案
  2. P102伯彥堆積木
    • 題目連結
    • 題目敘述：伯彥正在學習如何蓋出一座積木城堡，他知道為了讓這座城堡屹立不搖，每一層都要比上一層多疊兩個積木，且最上面那一層只有一個積木，但積木位於他想蓋的位置很遙遠，為了讓他一次就可以蒐集所有積木，請幫他計算若他要蓋$n$層城堡，他需要拿多少個積木
Back to top