遞迴課堂任務

• 先備知識：帕斯卡三角形。可參考維基百科、TED：帕斯卡三角形裡的數學秘密(可調繁體中文字幕)、巴斯卡三角形的幾個性質。
• 以進階程式練習帳密登入景美女中程式解題系統(JMJudge) > 加入競賽：Apcs課程-遞迴練習區。

a072. 啊就階乘，簡單吧>.0

遞迴思維建立

• 欲求
  $n!$ 的值，只要知道
  $(n-1)!$ 的值，再乘以
  $n$ ，即為所求。
• 請參考課本 2-2：遞迴函式，內有階乘函式的迴圈版本與遞迴版本。

範例程式碼

• 請嘗試改寫以上程式，輸入一正整數n，可輸出
  $n!$ 的值。
• 若將雙斜線處取消註解，程式可以計算並輸出總共呼叫fac()函式幾次。

a084. 偉晉的考驗

遞迴思維建立

• $C_r^n$：沒我的話，要從剩下
  $n-1$ 人選出
  $r$ 人；有我的話，要從剩下
  $n-1$ 人選出
  $r-1$ 人。
• 終止條件設定：如果不需再挑選任何人（
  $r=0$），或是人數剛好等於需要挑選的人數（
  $n=r$），挑選方法都只有一種。

範例程式碼

請嘗試改寫以上程式，輸入一兩個整數a、b，可輸出

$C_b^a$ 的值。

延伸練習：a054. 出來打球

Hints

• $P_r^n$：沒我的話，要從剩下
  $n-1$ 人選出
  $r$ 人；有我的話，我先選擇在
  $r$ 件球衣中穿哪一件，然後每種穿法都要再從剩下
  $n-1$ 人選出
  $r-1$ 人，繼續遞迴下去。
• 終止條件設定：
  • 如果不需再挑選任何人（
    $r=0$），挑選方法就只剩一種。
  • 如果人數剛好等於需要挑選的人數，那麼「我先選擇在
    $r$ 件球衣中穿哪一件」，然後每種穿法都要再從剩下
    $n-1$ 人選出
    $r-1$ 人，繼續遞迴下去。在這種狀況下，本問題即收斂成階乘問題。

a158. 長腿阿馨爬樓梯

遞迴思維建立

• f(int n)：代表 n 階樓梯可以有幾種不同的走法。
• 若選擇走一階，接下來的走法共有f(n-1)種；若選擇走兩階，接下來的走法共有f(n-2)種，以此類推。
• 假設阿馨只能走一階或兩階，那麼走法的總數會是「走了一階之後的走法 + 走了兩階之後的走法」。
• 終止條件設定：假設阿馨只能走一階或兩階，
  • 如果樓梯只有 1 階，只有 1 種走法。
  • 如果樓梯只有 2 階，共有 2 種走法（ 1+1 或 一次走 2 階）。

範例程式碼

假設阿馨只能走一階或兩階，寫法如下：

#include <iostream>
using namespace std;

int f(int n){
    if(n == 1){
        return 1;
    }
    if(n == 2){
        return 2;
    }
    return f(n-1) + f(n-2);
        //  1??      2??
}

int main(){
    cout << f(5) << endl;
}

請嘗試改寫以上程式，將走三階納入考量。

a160. 小妮爬樓梯（總次數上限版）

遞迴思維建立

• f(int n, int k)：代表 n 階樓梯只能跨兩階k次以內，可以有幾種不同的走法。
• 若選擇走一階，接下來的走法共有f(n-1, k)種；若選擇走兩階，「會用掉一次跨兩階的扣打」，那麼接下來的走法共有f(n-2, _____)種呢？
• 終止條件設定：
  • 如果樓梯只有 1 階，只有 1 種走法。
  • 如果樓梯只有 2 階，需要將 k 值納入考量。與上一題相比，如果還有跨兩階的扣打，會有幾種走法？如果跨兩階的扣打沒了，則剩下幾種走法？
  • 如果不是剩下 1 階或 2 階，但跨兩階的扣打沒了，那就只能走一階，此時n階的走法數量相當於n-1階的走法數量。

範例程式碼

#include <iostream>
using namespace std;

int f(int n, int k){ 
    if(n == 1){
        return 1;
    }
    if(n == 2){
        if(______){
            return _______;
        } else{
            return ________;
        }
    }
    if(k == 0){ 
        return f(n-1, k);
    }
    return f(n-1, k) + f(n-2, _____);
       
}

int main(){
    int N, K;
    cin >> N >> K;
    cout << f(N, K) << endl;
}

請嘗試填空以上程式，找出完整遞迴式，並根據k的值，決定還剩 2 階的走法。

延伸練習：a161. 小湊爬樓梯（連續次數上限版）

Hints

• 遞迴函式內，參數的意義改變了。n 代表有幾個階梯，k 則代表 還剩幾次連跳2階的扣打。
• 設立一全域變數，紀錄原始連跳2階的扣打。當遞迴函式內，呼叫了走 1 階的選擇，則將連跳 2 階的扣打值設為此全域變數。
• 若不想設立全域變數，亦可新增一個遞迴函式參數，存放原始連走 2 階的扣打。