---
# System prepended metadata

title: recursion 遞迴
tags: [程設班講義]

---

# 簡介
遞迴是函式呼叫自己本身的寫法，可以一層一層運算回傳。(手算時你就知道他的威力了。)

在函式中呼叫自己，並且要判斷結束，不然會無限遞迴。

呼叫後函式會先被放進 `Stack` 裡面，`Stack` 就像一疊盤子，不能從中間拿，最後放進去的會先被拿走，最先放進去的會被壓在最底下，所以最後被拿走。

所以先執行的會最後被回傳，最後執行的會先被回傳。

![Data_stack.svg](https://hackmd.io/_uploads/rJUDV5KKkg.png)

# 例子
## 連加
```cpp=
int f(int n) {
    if (n == 1)
        return 1 ;
    else
        return n + f(n - 1) ;
}
```

 `f(3)` 遞迴之後被分解成 `3 + f(2)`， `f(2)` 又被分解成 `2 + f(1)`， `f(1)` 到了結束的判斷所以代表 `1`。
 
`f(2)` 等於 `2 + f(1)` 也就代表 `2 + 1` 等於 `3`。

`f(3)` 等於 `3 + f(2)` 也就代表 `3 + 3` 等於 `6`。

所以呼叫 `f(3)` 會回傳 `6`。

![image](https://hackmd.io/_uploads/BkHfF62t1g.png)




## 階乘
```cpp=
int f(int n) {
    if (n == 1)
        return 1;
    else
        return n * f(n - 1);
}
```

 `f(3)` 遞迴之後被分解成 `3 * f(2)`， `f(2)` 又被分解成 `2 * f(1)`， `f(1)` 到了結束的判斷所以代表 `1`。
 
`f(2)` 等於 `2 * f(1)` 也就代表 `2 * 1` 等於 `2`。

`f(3)` 等於 `3 * f(2)` 也就代表 `3 * 2` 等於 `6`。

所以呼叫 `f(3)` 會回傳 `6`。

![image](https://hackmd.io/_uploads/B1gGt63Y1g.png)


## 次方
n 的 m 次方 ( $n^m$ )
### 遞迴
```cpp=
long long f(int n, int m) {
    if (m == 0)
        return 1;
    else{
        return n * f(n, m - 1);
    }
}
```

 `f(2,3)` 遞迴之後被分解成 `2 * f(2,2)`， `f(2,2)` 又被分解成 `2 * f(2,1)`， `f(2,1)` 再被分解成 `2 * f(2,0)`， `f(2,0)` 到了結束的判斷所以代表 `1`。
 
`f(2,1)` 等於 `2 * f(0)` 也就代表 `2 * 1` 等於 `2`。
 
`f(2,2)` 等於 `2 * f(1)` 也就代表 `2 * 2` 等於 `4`。

`f(2,3)` 等於 `2 * f(2)` 也就代表 `2 * 4` 等於 `8`。

所以呼叫 `f(2,3)` 會回傳 `8`。

![image](https://hackmd.io/_uploads/SyQyYThKke.png)


### 迴圈
```cpp=
long long f(int n, int m) {
    long long ans = n ;
    for (int i = 1 ; i < m ; i++) {
        ans *= n ;
    }
    return ans ;
}
```

## 費氏數列

```cpp=
long long f(int n) {
    if (n == 1)
        return 1 ;
    if (n == 2)
        return 1 ;

    return f(n - 1) + f(n - 2) ;
}
```
 `f(5)` 遞迴之後被分解成 `f(4) + f(3)`， `f(4)` 被分解成 `f(3) + f(2)`， `f(3)` 再被分解成 `f(2) + f(1)`， 在`f(1)` 、`f(2)`時結束判斷所以代表 `1`。
 
`f(3)` 等於 `f(2) + f(1)` 也就代表 `1 + 1` 等於 `2`。
 
`f(4)` 等於 `f(3) + f(2)` 也就代表 `2 + 1` 等於 `3`。

`f(5)` 等於 `f(4) + f(3)` 也就代表 `3 + 2` 等於 `5`。

所以呼叫 `f(3)` 會回傳 `5`。

![{F0196563-01D6-482B-BD5F-A379312A623F}](https://hackmd.io/_uploads/rku6QKoFJl.png)


### 費時數列
眾所周知，費氏數列之所以叫做費氏數列是因為他在用他計算時，時間複雜度會變成 $O(2^n)$ ，而電腦執行 $10^5$ 就需要超過一秒，所以他相當費時，才會叫做費時數列。(沒我開玩笑的。)

為了解決這個問題有以下幾種方法 : 
- 動態規劃 (DP) ------> $O(n)$
- 矩陣快速冪 ------> $O(log~n)$
- 黃金比例的通項公式 ------> $O(log~n)$

如果隔壁的進階教學還記得的話他會過來淺談後兩項。

# 例題

- [a421: Benson爬分](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a421)

- [a744: F. Q怎麼還在暈](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a744)

[a745: f91](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a745)

- [a870: 正方形](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a870)

- [b066: 好多好多的括號](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=b066)

###### 都看到這了難道不按個愛心支持一下嗎?