## 定義
在函數的定義中使用函數自身的方法，在數學上可以這樣表示
\begin{cases}
f(0) = 1\\
f(x) = x\ +\ f(x-1) \times 2，x\in N
\end{cases}
在上面的數學例子中，$f(1) = 1 + f(0)\times2 = 1 + 1\times2 = 3$
再舉一個實際的例子，假設我想知道我們家祖譜上的父輩祖先最早能溯源到誰
因為祖譜上只會寫**誰是某人的父親**，其他關係則**需要判斷**(例:爸爸的爸爸是爺爺)
我可以從我的爸爸 $F_0$ 先開始找，找到我爸爸後再去找我的爺爺 $F_1$
如此往復，到最後找到**沒有記載父親的人**就是祖譜上最早的父輩祖先
而對於大部分人來說，遞迴很重要的一點是 "能否打破順序執行的思考過程"
這點在河內塔可以得到驗證，也可以快速判斷一個人是否有天賦
## 開始前先介紹一個小工具
[Python動態顯示程式碼](https://pythontutor.com/python-debugger.html#mode=edit)
它可以一步步去生成程式碼的執行過程
可以幫助各位理解遞迴過程
如果遞迴的層數過大，它會報錯，請用**小測資幫助理解**就好
## $n!$ (正整數的階乘)
$n!$ 的定義所有小於等於該數的正整數的積，也可以簡單理解成 $n \times (n-1) \times\ ...\ \times 1$
所以 $n! = n \times (n-1)! = n \times (n-1) \times (n-2)!$， 後面以此類推
由於這樣的特性，我們可以對階乘做遞迴，首先就是要找出數學的遞迴式
\begin{cases}
\ 1! = 1\\
\ n! = n \times (n-1)!，x\in Z^+
\end{cases}
如果將 $n!$ 當成一個程式中的 function "A"，$n! = n \times (n-1)!$ 其實就是在 A 中呼叫 A
也就是最一開始在定義中提到的在函式中呼叫自己的方式，實際程式碼如下:
```cpp=
int rec(n) {
# 明確的終止遞迴條件
if (n == 1)
return 1 ;
# 持續重複function(呼叫自身的部分)
else if (n > 1)
return n * rec(n-1) ;
}
```
很明顯多了一個"終止遞迴條件"，因為數學的遞迴式當中也有同樣的東西 ($1! = 1$)
主要的原因是為了要**停止遞迴**(防止它無限遞迴下去)，所以必須設定**明確的終止目標**(base case)
base case 可能有很多種，最主要就是看你怎麼去定義你的遞迴式
比如在這個 case 當中你會發現，有沒有 $\times 1$ 結果都是一樣的
所以如果改寫成下面這個樣子也可以讓程式順利執行
```cpp=
int rec(n) {
# 明確的終止遞迴條件
if (n <= 2)
return n ;
# 持續重複function(呼叫自身的部分)
else if (n > 2)
return n * rec(n-1) ;
}
```
這樣的程式碼在處理 $n > 2$ 的情況下只會乘到 $2$，在 $n <= 2$ 時回傳 n
因為根據定義可以發現 $1! = 1, 2! = 2$，不過這樣寫有幾個問題
1. 複雜的 base case 更容易出錯
2. 在大部分情況很難想到
因此如果在數學的領域也好，程式的領域也罷，通常都是使用最直觀或最簡單的 base case
## 例題-ZJ c547. Bert 爬樓梯
[題目連結](https://zerojudge.tw/ShowProblem?problemid=c547)
解題思路 :
這題其實跟高中學過的排列組合經典題目很像，就像下面這張圖
如果有學過就知道，$A$ 往下和往右直走的答案都是 $1$，如果不是 $A$ 能直走到的位置
就是將上方+左方的點的答案相加，就會變成該點的答案數量
舉這個例子只是想告訴各位，某個點 $X$ 的答案 = "能用一步走到 $X$ 的位置 $Y$" 所有 $Y$ 的答案總和
那對於這個題目來說，可以一次爬一階或爬兩階，反推來說就是可以退一階或退兩階
簡單講就是"只有第 $X-1$ 階和第 $X-2$ 階能夠一步走到第 $X$ 階"
加上上面的例子最後得出的結論，我們可以列出遞迴式
\begin{cases}
f(1) = 1 \\
f(2) = 2 \\
f(x) = f(x-1) + f(x-2),\ n \ge 3
\end{cases}
但這題還有需要注意的地方，就是題目是重複輸入數字去找
如果每次都給最大的測資，那跑起來速度會很慢，如果我們能夠一邊計算一邊記錄結果
那之後就可以省略計算的部分，直接拿之前計算的結果來用就可以了
```cpp=
int rec(int n) {
if (ways[n]) // 如果已經算過
return ways[n] ; // 直接回傳
ways[n] = (rec(n-1) + rec(n-2)) % mod ;
return ways[n] ; // 記得取餘
}
```
這裡的 base case 已經融入在 ways 陣列當中了，所以不需要特別寫出來
不過因為 $n$ 最大是 $10000$，所以一次計算完 $10000$ 階，其他也能計算完
```cpp=
#include<bits/stdc++.h>
using namespace std ;
#define mod 1000000007
int ways[10005] ;
int rec(int n) {
if (ways[n]) // 如果已經算過
return ways[n] ; // 直接回傳
return ways[n] = (rec(n-1) + rec(n-2)) % mod ; // 記得取餘
}
int main() {
ios::sync_with_stdio(0), cin.tie(0) ;
// 前兩階用推的 其餘為遞迴式
ways[1] = 1 ;
ways[2] = 2 ;
rec(10000) ; // 一次計算完
int n ;
while (cin >> n)
cout << ways[n] << '\n' ;
return 0 ;
}
```
## 例題-ZJ e357. 遞迴函數練習
[題目連結](https://zerojudge.tw/ShowProblem?problemid=e357)
解題思路 :
直接把數學的遞迴式拿來用，base case 就是 `if (x = 1) return 1 ;`
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int f(int x) {
if (x == 1) return 1 ;
if (x % 2 == 0) return f(x/2) ;
return f(x-1)+f(x+1) ;
}
int main() {
int x ;
cin >> x ;
cout << f(x) ;
return 0 ;
}
```
```python=
def main() :
def f(x) :
if (x == 1) : return 1
if (x % 2 == 0) : return f(x//2)
return f(x-1) + f(x+1)
x = int(input())
print(f(x))
main()
```
## 例題-TCIRC 合成函數(2) (APCS201902)
[題目連結](https://judge.tcirc.tw/problem/d002)
解題思路 :
首先要先列出遞迴式
* f(x)=2x–3
* g(x,y)=2x+y–7
* h(x,y,z)=3x–2y+z
因為範例輸入中只要把數字帶入函式算出來就好
並**不會出現無限遞迴**的情形，所以沒有 base case
而輸入的情形只有四種: "f" "g" "h" "數字"
所以我們只要用 if 就可以解出答案
不過對於大多數人來說最大的問題不是在這裡，而是在如何依照題目要求的順序運算
假設有一組測資 `g 1 2` 那當然很簡單，直接輸入 g 跟兩個數字即可
但是如果測資比較複雜，比如 `h f 5 g 3 4 3`，用數學的概念是 $h(f(5), g(3, 4), 3)$
其實觀察可以發現最主要的困難點就是"如何判斷輸入數字/函式的層級"
在上面比較複雜的例子當中，函式 f 跟 g 都是在第二層，函式 h 則是在第一層
遞迴是可以做到同樣的效果的，假設我們有一個程式可以判斷輸入是函式還是數字，並將其計算完成
那在我遇到函式 f 時，是不是可以呼叫"一次"這個程式碼，這樣我就知道 $f(x)$ 中的 $x$，便可以算出 $f(x)$
那推廣到三個函式跟數字，這個程式要處理什麼函式，就看它有幾個未知數需要找，就執行這個程式幾次
(如有需要可以用畫圖理解不同函式、數字之間的遞迴 level 關係，有助於學習)
實際的程式碼如下 :
```cpp=
#include<bits/stdc++.h>
using namespace std ;
typedef long long LL ;
LL rec() {
string c ;
cin >> c ;
if (c == "f") // 遇到 f 函式
return 2*rec() - 3 ;
else if (c == "g") // 遇到 g 函式
return 2*rec() + rec() - 7 ;
else if (c == "h") // 遇到 h 函式
return 3*rec() - 2*rec() + rec() ;
else // 遇到數字
return stoi(c) ; // stoi 是把 string 轉成數字
}
int main() {
ios::sync_with_stdio(0), cin.tie(0) ;
cout << rec() << '\n' ;
return 0 ;
}
```
```python=
def main() :
def rec(idx) :
if list1[idx] == "f" :
x, idx = rec(idx+1)
return 2*x - 3, idx
elif list1[idx] == "g" :
x, idx = rec(idx+1)
y, idx = rec(idx+1)
return 2*x + y - 7, idx
elif list1[idx] == "h" :
x, idx = rec(idx+1)
y, idx = rec(idx+1)
z, idx = rec(idx+1)
return 3*x - 2*y + z, idx
else :
return int(list1[idx]), idx
idx = 0
list1 = input().split()
ans, idx = rec(idx)
print(ans)
main()
```
這邊同樣要注意，C++ 的輸入可以遇到空白就停止，而python只有**遇到換行(\n)才能停止**
所以我們必須**用index去指定位置** (index local 或 global 皆可)
再來，python有一個內建函式 **isdigit()** 可以判斷字串是否是數字，但是它**並不能判斷負數**
所以我直接**不判斷數字**，先判斷 f g h 的可能，剩下的那一個可能**只能是數字**，所以用 else
C++ 可以用 stoi() (string to integer) 將字串轉成整數，python 用 int() 即可
## 例題-ZJ d672. 10922 - 2 the 9s
[題目連結](https://zerojudge.tw/ShowProblem?problemid=d672)
這題的題目敘述有點糟糕，所以我再重新整理一次 9-degree 的部分
9-degree 總共有幾個，要看數字各位數能加總幾次(加總直到數字 $< 10$ 以內)
最後的次數就是 9-degree，比如 $837 \rightarrow 18 \rightarrow 9$ 總共加總兩次，所以 $837$ 的 9-degree 為 $2$
解題思路 :
這題主要看兩個輸出，第一個是 $n$ 是否為 $9$ 的倍數
這個非常簡單，我們只需要將各位數加總起來然後判斷是否為 $9$ 的倍數
```cpp=
string s ;
cin >> s ;
int num = 0 ; // 各位數加總的結果
for (char it: s) // 一個個位數加總
num += it - '0' ; // 字元轉數字(ASCII)
if (num % 9 != 0) // 判斷為"不是" 9 的倍數
cout << s << " is not a multiple of 9.\n" ;
else { // 是 9 的倍數
// 計算 9-degree
}
```
```python=
s = input()
if (s == "0") : return
num = 0
for it in s :
num += int(it)
if (num % 9 != 0) :
print(f"{s} is not a multiple of 9.")
else :
## 計算 9-degree
```
接下來就是用遞迴重複做加總的動作，最開始肯定要找 base case
其實題目有說只要算到 $< 10$ 就結束，就是這題的 base case
那接下來只剩下如何加總數字各位數
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int rec(int num, int degree) {
int next_n = 0 ;
if (num >= 10) // 還可以繼續遞迴
degree++ ;
else // base case
return degree ;
while (num) { // 加總各位數字
next_n += num % 10 ;
num /= 10 ;
}
return rec(next_n, degree) ; // 進入下一層遞迴
}
int main() {
ios::sync_with_stdio(0), cin.tie(0) ;
string s ;
while (cin >> s && s != "0") {
int num = 0, degree = 0 ;
for (char it: s) // 一個個位數加總
num += it - '0' ; // 字元轉數字(ASCII)
if (num % 9 != 0) // 判斷為"不是" 9 的倍數
cout << s << " is not a multiple of 9.\n" ;
else { // 是 9 的倍數
degree = rec(num, 1) ;
cout << s << " is a multiple of 9 and has 9-degree " << degree << ".\n" ;
}
}
return 0 ;
}
```
```python=
def main() :
def rec(num, degree) :
n = 0
if (num >= 10) : degree += 1 # 可以繼續遞迴
else : return degree # base case
while (num) : # 加總各位數
n += num % 10
num //= 10
return rec(n, degree)
while (True) :
s = input()
if (s == "0") : return # 結束輸入
num = 0
for it in s :
num += int(it)
if (num % 9 != 0) :
print(f"{s} is not a multiple of 9.")
else :
degree = rec(num, 1)
print(f"{s} is a multiple of 9 and has 9-degree {degree}.")
main()
```
## 例題-ZJ c129. 00572 - Oil Deposits
[題目連結](https://zerojudge.tw/ShowProblem?problemid=c129)
(建議先學過基礎圖論-DFS、BFS再解這題)
解題思路 :
題目說含有石油的小塊只要相連，就被分為同一個 oil deposit，要找圖中有幾個 oil deposit
其實就是當找到一塊新的 oil deposit 時，用 DFS/BFS 去將同 oil deposit 的地方消掉
因為如果不要再次遇到同個 oil deposit 的 pocket，那只有將遇過的 pocket 改成不含石油
以下是用 DFS 解題的程式碼 (BFS 不是遞迴)
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int n, m ;
char G[105][105] ;
void rec(int x, int y) {
G[x][y] = '*' ; // 找到了就消除(改成不含石油)
// 用踩地雷的相連(某格周遭8格)
for (int i=-1;i<=1;i++) {
for (int j=-1;j<=1;j++) {
int nx = x+i, ny = y+j ;
if (nx >= 0 && nx < n && ny >= 0 && ny < m)
if (G[nx][ny] == '@')
rec(nx, ny) ;
}
}
return ;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0) ;
while (cin >> n >> m && n && m) {
// 輸入圖
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
cin >> G[i][j] ;
int ans = 0 ; // 有幾個 pocket
for (int i=0;i<n;i++) {
for (int j=0;j<m;j++) {
if (G[i][j] == '@') { // 新的 pocket
ans++ ;
rec(i, j) ;
}
}
}
cout << ans << '\n' ;
}
return 0 ;
}
```
## 類似題-ZJ d165. 八、草場普查
[題目連結](https://zerojudge.tw/ShowProblem?problemid=d165)
解題思路 :
(建議先學過基礎圖論-DFS、BFS再解這題)
這題跟前一題一樣，草場的數量就是 oil deposit 的數量，不過這題還有某草場最大蘊藏量
簡單來說就是要在消去的同時計算數量，比如在這題中就需要在某個遞迴中回傳其延伸的草場蘊藏量
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int n, m ;
int G[105][105] ;
int mm[4][2] = {{0, 1},{1, 0},{0, -1},{-1, 0}} ; // 上下左右
int rec(int x, int y) {
G[x][y] = 0 ; // 記得走過要去除
int leaf = 0 ; // 上下左右延伸後的結果
for (int i=0;i<4;i++) { // 往四個方向走
int nx = x+mm[i][0], ny = y+mm[i][1] ;
if (nx >= 0 && nx < n && ny >= 0 && ny < m)
if (G[nx][ny])
leaf += G[nx][ny] + rec(nx, ny) ; // 延伸草場蘊藏量
}
return leaf ;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0) ;
while (cin >> n >> m) {
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
cin >> G[i][j] ;
int cnt = 0, ans = 0 ; // 數量、最大蘊藏量
for (int i=0;i<n;i++) {
for (int j=0;j<m;j++) {
if (G[i][j]) { // 新的草場
cnt++ ;
ans = max(ans, G[i][j] + rec(i, j)) ;
}
}
}
cout << cnt << '\n' << ans << '\n' ;
}
return 0 ;
}
```
## 例題-ZJ f637. DF-expression
[題目連結](https://zerojudge.tw/ShowProblem?problemid=f637)
解題思路 :
這題首先就是要釐清每個功能與其執行後的結果，功能有 $0, 1, 2$ 三個
$0$ 是代表目前的正方形(邊長 $n$)中，每個格子都是黑色(有 $n\times n$ 個格子是黑色)
$1$ 是代表目前的正方形(邊長 $n$)中，每個格子都是白色(有 $n\times n$ 個格子是白色)
$2$ 是代表目前的正方形(邊長 $n$)切割成四塊，然後接著依序處理這四塊的功能
因為切割成四塊，所以邊長會變成 $n/2$，但通常遞迴中兩個變數都會是 $n$
只要記得在不同層級中的遞迴，同名變數可能代表的實際數字不同，簡單看下方表格
這個表格就是字串中的數字與"遇到該數字時"的邊長、遞迴層級、黑色面積、總面積
結合表格與前面的解說，大概可以知道遇到不同數字時該如何運作
如果遇到 $0$，因為沒有增加黑色的面積，也沒有切割，所以不需要特別操作
如果遇到 $1$，增加了黑色面積，而且增加當下的邊長 $n \times n$ 格
如果遇到 $2$，要將目前的正方形切割成四塊，邊長減半，還要處理四個小塊
所以用程式碼大概會像是這樣
```cpp=
void rec(int n) {
if (s[idx] == '1') // 像素 1
ans += n*n ;
else if (s[idx] == '2') {
for (int i=0;i<4;i++) { // 平分成四塊
idx++ ;
rec(n/2) ; // 邊長/2 並一一處理
}
}
}
```
因為我是用字串儲存操作的數字，所以要用一個 idx 代表 index
才能知道目前要做的操作是哪個，然後用 ans 紀錄總面積
```cpp=
#include<bits/stdc++.h>
using namespace std ;
string s ; // DF-expression
int ans, idx ; // 像素 1 數量、index
void rec(int n) {
if (s[idx] == '1') // 像素 1
ans += n*n ;
else if (s[idx] == '2') {
for (int i=0;i<4;i++) { // 平分成四塊
idx++ ;
rec(n/2) ; // 邊長/2 並一一處理
}
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0) ;
int n ;
// 重複輸入(可以一次輸入多個側資)
// 不用重複編譯執行
while (cin >> s >> n) {
ans = idx = 0 ;
rec(n) ;
cout << ans << '\n' ;
}
return 0 ;
}
```
## 例題-TCIRC 棍子中點切割
[題目連結](https://judge.tcirc.tw/problem/d003)
(建議先學過排序基礎-二分搜後再開始解題)
解題思路 :
題目說機器可切割的點都是固定的，會計算出最接近中點的切割點，並照此切割點切成兩段
其實如果仔細去想，因為只有切割點可以被切割，所以切割後的棍子前後端
只有可能會是"一開始的左端"、"一開始的右端"、"指定的任意切割點"
所以如果把所有可能的左右端都放進同一個陣列，比如以下的陣列
| index | 0 | 1 | 2 | 3 | 4 | 5 |
| --- | ---- | ---- | ---- | --- | --- | --- |
| 左右端 | 0 | 1 | 2 | 4 | 6 | 10 |
這樣在找最接近中點的切割點時，會比較方便，因為可以用 `(A[left]+A[right])/2` 表示
要處理某個棍子就會需要依照這個順序
1. 判斷還能不能切割(兩端點中有無切割點) (base case)
2. 計算中點
3. 找出最靠近中點的切割點
4. 計算目前這根棍子的切割成本
5. 計算切割完後變成左右兩根棍子的切割成本
執行順序會像是 : $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 1 ...$
用程式碼的話會像是下面這樣
```cpp=
int cp[50005] ; // cut point(左右端)
int cut(int L, int R) { // left、right
if (R-L <= 1) return 0 ; // 兩點中已無切點
int k = (cp[R]+cp[L]) / 2 ; // 中點
int dis = R - L, m ; // dis 與中點距離、m 最靠近中點座標
for (int i=L+1;i<R;i++) {
if (abs(cp[i]-k) < dis) {
dis = abs(cp[i]-k) ;
m = i ;
}
}
// 目前切割成本 + 左半邊總成本 + 右半邊總成本
return cp[R]-cp[L] + cut(L, m) + cut(m, R) ;
}
```
不過有一個問題，就是如果每次都用線性搜尋的話，時間複雜度有點太高了
簡單計算一下，如果有 n 個切點(包含左右端)，大概就會是 $n\log(n)$
因為這次的切點剛好是已排序的，並且剛好是在同一個陣列中，非常適合二分搜
二分搜通常是找 $\ge$ 中點的第一個點，因為這裡是找最靠近中點的切割點
所以還要找 $\le$ 中點的第一個點，也就是二分搜完後的那個點左邊的點
```cpp=
#include<bits/stdc++.h>
using namespace std ;
typedef long long LL ;
LL cp[50005] ;
LL cut(int L, int R) {
if (R-L <= 1) return 0 ; // 兩點中已無切點
LL k = (cp[R]+cp[L]) / 2 ; // 中點
// 找出第一個 >= k 的
int m = lower_bound(cp+L, cp+R, k) - cp ;
if (cp[m-1]-cp[L] >= cp[R]-cp[m]) // 左邊切點更靠近
m-- ;
// 目前切割成本 + 左半邊總成本 + 右半邊總成本
return cp[R]-cp[L] + cut(L, m) + cut(m, R) ;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0) ;
int N, L ;
cin >> N >> L ;
cp[0] = 0 ; // 兩端當作切點會比較好做
cp[N+1] = L ;
for (int i=1;i<=N;i++)
cin >> cp[i] ;
cout << cut(0, N+1) << '\n' ;
return 0 ;
}
```
## 例題-ZJ e183. 10940 - Throwing cards away II
[題目連結](https://zerojudge.tw/ShowProblem?problemid=e183)
解題思路 :
這題如果要最簡單的解法是用 queue 去做模擬，但實際上這題是數論的題目
先從比較小的測資去看一下有沒有辦法整合出規律
* $n = 1\rightarrow 1$
* $n = 2\rightarrow 2$
* $n = 3\rightarrow 2,3\rightarrow 3,2\rightarrow 2$
* $n = 4\rightarrow 2,3,4\rightarrow 3,4,2\rightarrow 4,2\rightarrow 2,4\rightarrow 4$
* $n = 5\rightarrow\ ...\rightarrow 2$
* $n = 6\rightarrow\ ...\rightarrow 4$
* $n = 7\rightarrow\ ...\rightarrow 6$
* $n = 8\rightarrow\ ...\rightarrow 8$
其實可能已經有人看出來了，大致上會變成以下這種結果
如果是偶數，比如 $n=6$，在丟棄保留幾次後會變成 $2,4,6$，剛好就是 $n=3$ 的兩倍
再看看 $n=12$，在丟棄保留幾次後會變成 $2,4,6,8,10,12$，剛好是 $n=6$ 的兩倍
如果再進一步丟棄保留，會變成 $4,8,12$，剛好是 $n=3$ 的四倍
因為丟棄保留的規則一樣，所以如果 $n$ 是偶數，結果就是 $n/2$ 結果的兩倍
如果是奇數($n > 1$)，就比較特殊了，可以拿幾個例子來看，比如 $n=3,5,7,9,11,13$
$n = 3 \rightarrow 2$
$n = 5 \rightarrow 5,2,4\rightarrow 2$
$n = 7 \rightarrow 7,2,4,6\rightarrow 6$
$n = 9 \rightarrow 9,2,4,6,8\rightarrow 2$
$n = 11 \rightarrow 11,2,4,6,8,10\rightarrow 6$
$n = 13 \rightarrow 13,2,4,6,8,10,12\rightarrow 10$
如果 $n=5$，經過幾次丟棄保留會剩下三個，但是跟 $n=6$ 不一樣，第一項變成 $5$
觀察 $n=$ 其他奇數也一樣，經過幾次保留會變成 $n,2,4,...$，項數是 $(n+1)/2$
既然項數一樣，是不是也可以找到規律，如果去找 $n$ 與 $(n+1)/2$ 的關係，比如 $n=5$
$n=5$ 的結果是 $2$，$n=(5+1)/2=3$ 的結果是 $2$
$n=7$ 的結果是 $6$，$n=(7+1)/2=4$ 的結果是 $4$
$n=9$ 的結果是 $2$，$n=(9+1)/2=5$ 的結果是 $2$
$n=11$ 的結果是 $6$，$n=(11+1)/2=6$ 的結果是 $4$
應該能看出 `f(n) = 2*(f((n+1)/2)-1)`，如果真的不行也可以多舉幾個例子
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int p[500001] ; // 算過的結果
int f(int a) {
if (p[a]) return p[a] ; // 已經算過
if (a == 1) return 1 ;
if (a%2 == 0) // 偶數
return p[a] = 2*f(a/2) ;
else // 奇數
return p[a] = 2*(f((a+1)/2)-1) ;
}
int main(){
ios::sync_with_stdio(0), cin.tie(0) ;
int n ;
while(cin >> n && n) // 重複輸入
cout << f(n) << '\n' ;
return 0 ;
}
```
有興趣的可以去看 Josephus problem，應該會有更詳細的推論跟更廣泛的問題討論
## 河內塔
河內塔是遞迴中滿重要的一個例子，按照維基百科的敘述
有三根杆子 $A，B，C$，$A$ 杆上有 $N(N>1)$ 個穿孔圓盤，盤的尺寸由下到上依次變小
要按下列規則將所有圓盤從 A 杆移至 C 杆，問最少須多少步驟
1. 每次只能移動一個圓盤
2. 大盤不能疊在小盤上面
(圖片等請自行查詢，網路上有很多靜態或動態的表現都很不錯)
我們可以先看圓盤比較少的情況，先討論 $1~3$ 個圓盤
先看 $1$ 個圓盤，直接從 $A \rightarrow C$ 即可
$2$ 個圓盤(小、大)，先把小圓盤從 $A \rightarrow B$，再把大圓盤從 $A \rightarrow C$，最後把小圓盤從 $B \rightarrow C$
$3$ 個圓盤，這個就比較特殊了，如果我們拆開來想，把最大的圓盤跟上面兩個分開
這樣我們只要想辦法把上面兩個圓盤先移到 $B$，然後把最大的圓盤移到 $C$
最後只要把上面兩個圓盤從 $B \rightarrow C$
其實如果你觀察力不錯的話會發現兩個圓盤也是這個概念
把 "最下方的圓盤" 跟 "其餘圓盤" 拆開做移動，不過可能會有人有疑問
如何把兩個圓盤從 $B$ 移到 $C$，其實跟 $A \rightarrow C$ 一樣，只是位置稍微修改而已
那對於 $N \ge 2$ 的情況，其實都能用拆分移動的方法
拆分後的上方就是討論移動 $N-1$ 從 $A \rightarrow B$ 跟從 $B \rightarrow C$ 的情況
拆分後的下方就是討論移動第 $N$ 個圓盤從 $A \rightarrow C$ 的情況
所以如果需要一個遞迴式去計步數，應該會像是下面這樣
$\begin{cases}
f(a,b,c,1) = 1 \\
f(a,b,c,n) = f(a,c,b,n-1)+f(b,a,c,n-1)+1
\end{cases}$
要注意這裡的 $a,b,c$ 是指 "起點,暫存點,終點"，暫存點就是可能會暫時放在該位置
但最後一定都是 "原本都在起點" 到 "全都在終點"，再來看看程式碼
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int rec(char a, char b, char c,int n) {
if (n == 1) { // n == 1 直接從 A 到 C
cout << "move 1 from " << a << " to " << c << '\n' ;
return 1 ;
}
// 拆分成上下兩部分
int cnt = 1 ; // 先把下方從 A 到 C 的移動加進去
cnt += rec(a, c, b, n-1) ; // 上方從 A 到 B
// 下方從 A 到 C
cout << "move " << n << " from " << a << " to " << c << '\n' ;
cnt += rec(b, a, c, n-1) ; // 上方從 B 到 C
return cnt ;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0) ;
int n ;
cin >> n ;
cout << rec('A', 'B', 'C', n) << '\n' ;
return 0 ;
}
```
通常河內塔的問題最基礎也會問移動的步驟，以上程式碼就是移動步驟+移動次數
如果只問移動次數的，其實可以用數學做推導，只要把遞迴式通解算出來就好
河內塔其實還有一些延伸的概念，但不在遞迴的概念內或太難的我就跳過了
Sign in with Wallet
Connect another wallet