# 簡介
遞迴是函式呼叫自己本身的寫法，可以一層一層運算回傳。(手算時你就知道他的威力了。)
在函式中呼叫自己，並且要判斷結束，不然會無限遞迴。
呼叫後函式會先被放進 `Stack` 裡面，`Stack` 就像一疊盤子，不能從中間拿，最後放進去的會先被拿走，最先放進去的會被壓在最底下，所以最後被拿走。
所以先執行的會最後被回傳，最後執行的會先被回傳。
# 例子
## 連加
```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`。
## 階乘
```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`。
## 次方
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`。
### 迴圈
```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`。
### 費時數列
眾所周知，費氏數列之所以叫做費氏數列是因為他在用他計算時，時間複雜度會變成 $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)
###### 都看到這了難道不按個愛心支持一下嗎?
Sign in with Wallet
Connect another wallet