# 遞迴課堂任務

- 先備知識：帕斯卡三角形。可參考[維基百科](https://zh.wikipedia.org/zh-tw/%E6%9D%A8%E8%BE%89%E4%B8%89%E8%A7%92%E5%BD%A2)、[TED：帕斯卡三角形裡的數學秘密](https://www.ted.com/talks/wajdi_mohamed_ratemi_the_mathematical_secrets_of_pascal_s_triangle/transcript?language=zh-tw&subtitle=zh-tw)(可調繁體中文字幕)、[巴斯卡三角形的幾個性質](https://www.sec.ntnu.edu.tw/uploads/asset/data/6256410b381784d09345bd5c/3.pdf)。
- 以進階程式練習帳密登入[景美女中程式解題系統(JMJudge)](https://jmj.cmgsh.tp.edu.tw/) > 加入競賽：Apcs課程-遞迴練習區。

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

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

### 範例程式碼

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

## a084. 偉晉的考驗

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

### 範例程式碼

請嘗試改寫以上程式，輸入一兩個整數`a`、`b`，可輸出 $C^a_b$ 的值。

## 延伸練習：a054. 出來打球
### Hints
- $P^n_r$：沒我的話，要從剩下 $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 階的扣打。