<style>
body{
background-attachment: fixed;
background-repeat: no-repeat;
background: -webkit-linear-gradient(left, #ffffff,rgba(51,51,51,0.5)), url("https://i.imgur.com/NZiHUtv.jpg") center no-repeat fixed;
};
</style>
#### MDCPP進階組講義
## 遞迴 Recursion
作者：LittlePants
----
### 何謂遞迴？
- 遞迴就是大事化小，小事化無
- 遞迴的精隨是什麼？你要相信他是對的
- 遞迴暴搜可以解決一切，但是可能必須等到世界毀滅
---
### 基本概念
- 數學上：函數直接或間接已自己定義自己
- 程式上：一個函數會直接或間接的呼叫自己
----
遞迴是一個很重要的程式結構
很多演算法都會用到遞迴的概念（DFS, DP）
但遞迴思考的方式比較特殊
藉由求出答案與子問題的關係，來回推出答案
----
但學習遞迴是非常必要且基礎的
我們會先用階乘來簡單講解一下遞迴
----
我們都知道 $N! = 1 \times 2 \times 3 ... N$
我們定義一個函數 $f(X)$ 代表 X!
----
那麼可以這樣定義 $f(N) ＝ N * f(N-1)$ 當 $n > 1$
如果你想知道$f(3)$是多少，你必須先算出$f(1),f(2)$
----
步驟如下
$f(3) = 3 * f(2)$
$f(2) = 2 * f(1)$
$f(1) = 1$
所以要得到$f(3)$的值
我們需要先把問題化簡到1再回推
----
### 我們來用程式寫寫看
```cpp
int f(int x){
if(x == 1) return 1; // 中止條件（邊界條件）
return x * f(x-1); // 遞迴轉移
}
```
----
### 寫遞迴有兩個重點
- 遞迴如何轉移
- 遞迴中止條件
----
也就是說
只要想出上面兩點你就可以把遞迴打出來了
我們來做個簡單的練習
[簡單費氏數列](http://mdcpp.mingdao.edu.tw/problem/B001)
（請大家不要使用迴圈做出這題)
----
參考code :
``` cpp
int f(int n){
if(n < 0) return 0;
if(n == 1 or n == 0) return 1; // 中止條件
return f(n-1) + f(n-2); // 遞迴轉移
}
```
----
我們會發現
使用上面程式執行效率會非常低
有可能是因為大量呼叫函數會花掉一些時間
但主要是因為有一大部分被重複計算了
----
我們看看當我們呼叫$f(6)$的情況
圖片網址 : http://blog.csdn.net/u013309870
----
有一大部份被重複計算了
當測資越大 被重複計算的次數也會越多
這是非常沒有效率的
所以我們會使用一個~~由蔣公提出來的方法~~的有效方法
----
## 用空間換取時間(記憶化)
----
我們多開一個陣列紀錄每個數字的答案
如果已被執行過就可直接回傳答案
廢話不多說 直接上程式碼
----
```cpp
int t,n,fab[200];
int f(int n){
if(n < 0) return 0;
if(fab[n]) return fab[n]; //記憶化
return fab[n] = (f(n-1) + f(n-2)); // 本code文眼
}
signed main(){
fab[0] = fab[1] = 1;
cin >> n;
cout << f(n) << '\n';
}
```
----
相信各位到次為止已經對遞迴有了初步的認識
但遞迴的用處遠遠不只如此
它還可以做到一些迴圈做不到的事
---
## 經典應用
---
## 求解 GCD(最大公因數)
----
要求gcd我們通常會用到一個家喻戶曉的演算法
----
## 歐幾里得演算法
也就是輾轉相除法
----
這個演算法大家小學時該都有學過
我來幫大家複習一下
----
```cpp
輾轉相除法
| 540 | 840 |
1 | 300 | 540 | 1
|-----|-----|
| 240 | 300 |
4 | 240 | 240 | 1
|-----|-----|
| 0 | 60 |
```
----
假設給們兩個數a,b要求他們的最大公因數
如果 b 能整除 a 那最大公因數就是 b
否則就讓 b = a % b , a = 原本的 b
一直做直到 b 能整除 a
----
簡單來說就是
- $\gcd(a,b)=\gcd(a,b-a)=\gcd(a,b \% a)$
----
有沒有一點遞迴的感覺
終止條件是 a % b == 0
否則就一直將 a , b 變小
透過數學證明我們可以知道
歐幾里得算法的時間複雜度是$O(log(min(a,b)))$
----
阿具體要怎麼做呢?
我們來看一下程式碼
----
參考 code(遞迴)
```cpp
int gcd(int a,int b){
if(b == 0) return a;
return gcd(b,a%b);
}
```
就是這麼短
但你要相信他是對的
----
但遞迴很慢啊
有沒有其他打法
----
參考 code(非遞迴毒瘤打法)
```cpp
int gcd(int a,int b){
while( (a%=b) and (b%=a) ) ;
return a | b; // 這裡的 | 可以改成 +
}
```
這是C語言最短的打法
但C++可以更短
----
```cpp
int gcd(int a,int b){
return __gcd(a,b);
}
```
???這個__gcd()是甚麼???
這是某些版本的C++會內建的函數
他不是標準函數所以前面會加上兩個底線
---
## 經典例題講解
---
---
### [河內塔](http://mdcpp.mingdao.edu.tw/problem/B011)
----
相信各位小時候都有玩過河內塔
它跟遞迴也有一些關聯
----
每次我們要把N個圓環移到目標柱子上時
我們會先把上面N-1個圓環移到非目標柱子上
然後再把第N個圓環移到目標柱子上
在把上面N-1個圓環放到N上面
----
只要弄清楚了目標柱與非目標柱
我們就可以打出下面的程式碼
----
```cpp
#include<bits/stdc++.h>
using namespace std;
void tow(int num, string A, string B, string C){
if (num == 0 ) return ;
tow(num-1, A, C, B); // 上面N-1個圓環移到非目標柱子上
cout << "Ring " << num << " from " << A << " to " << C << "\n";
// 移動第N個圓盤到目標柱上
tow(num-1, B, A, C); // 在把上面N-1個圓環放到N上面
}
int main(){
int n;
cin >> n;
tow(n ,"A","B","C");
}
```
---
### [合成函數(APCS考題)](http://mdcpp.mingdao.edu.tw/problem/B007)
----
合成函數的意思就是他傳入的參數有可能是數字或是函數
所以這題的參數只有3種情況f,g,或是數字
----
如果輸入的是數字就可以直接使用
如果輸入的是f就需要再往後讀一格
如果輸入的是g則需要往後讀兩格
----
按照上面的想法我們直接在函數中進行輸入
參考 code:
```cpp
#include<bits/stdc++.h>
using namespace std;
string c;
int sol(){
cin >> c;
int res = 0;
if(c[0] == 'f'){
res = 2 * sol() - 1;
} else if(c[0] == 'g'){
res = sol() + 2 * sol() - 3;
} else {
return stoi(c);
}
return res;
}
signed main(void){
cout << sol() << '\n';
}
```
----
上面的code我用到了一個函數 stoi
功能就是把 string 轉成 int
同理也有 stol 和 stoul
----
回家作業
[合成函數(困難)](http://mdcpp.mingdao.edu.tw/problem/B009/)
---
### [分形](http://mdcpp.mingdao.edu.tw/problem/B003)
圖片來源 : wiki
----
對於這題我們不需要研究什麼是分形
我們只需要觀察規律就好
----
我們會發現每增加一級
X的數量會變成原來的5倍
而長寬則會變成原本的3倍
----
```cpp
X // X數量為 1 邊長為 1
---
X X
X
X X // X數量為 5 邊長為 3
---
X X X X
X X
X X X X
X X
X
X X
X X X X
X X
X X X X // X數量為 25 邊長為 9
```
----
透過以上觀察
我們來遞迴定義一下這個分形
我們用$b(x)$來當作我們的函數
$b(n)$代表n級的盒子
----
我們知道 $b(1)$ = x
而 $b(n)$ 遞迴定義就是
``` cpp
b(n - 1) b(n - 1)
b(n - 1)
b(n - 1) b(n - 1)
```
----
最後我們只需要觀察出盒子之間的距離
就可以開始打了
這部份就讓同學自己思考看看吧
hint : 提供兩種方法求3的n次方
1. 可以用 pow(3, n)
2. 蓋一個表 pow[n] = 3的 n 次
----
參考 code (從中間擴散):
```cpp
#include<bits/stdc++.h>
using namespace std;
int T,n;
bool mat[2000][2000];
void sol(int x,int y,int n){
if(n == 1){
mat[x][y] = 1; //標記此格為X
return ;
}
int k = pow(3,n-2);
sol(x+k,y+k,n-1); //右下
sol(x+k,y-k,n-1); //右上
sol(x,y,n-1); //中間
sol(x-k,y+k,n-1); //左下
sol(x-k,y-k,n-1); //左上
}
signed main(){
cin >> T;
while(T--){
cin >> n;
int len = pow(3,n-1), k = (len+1)/2;
sol(k,k,n);
for(int i = 1; i <= len; i++)
for(int j = 1; j <= len; j++){
cout << (mat[i][j] == 1 ? "X" : " ");
if(j == len) cout << '\n';
}
cout << "---\n";
}
}
```
----
參考 code (從左上開始) :
by ICEYLEMON
``` cpp
#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define pb push_back
#define vi vector<int>
#define f first
#define s second
#define pii pair<int, int>
#define mod 1000000007
#define MOD(x) ((x)%mod + mod)%mod
#define all(x) x.begin(), x.end()
#define mem(x, a) memset(x, a, sizeof(x))
#define LOLI ios_base::sync_with_stdio(0), cin.tie(0)
#define loli
#ifdef loli
#define bug(x, n) for(int tt = 1; tt <= n; tt ++) cout << x[tt] << " ";cout << "\n";
#else
#define bug(x, n)
#endif
using namespace std;
const int maxn = 5e3 + 50;
char mp[maxn][maxn];
int power[100];
void init(){ // 蓋3的n次表
power[0] = 1;
for(int i = 1; i <= 10; i ++){
power[i] = power[i - 1] * 3;
}
}
void draw(int x, int y, int p){
for(int i = x + 1; i <= x + p; i ++){
for(int j = y + 1; j <= y + p; j ++){
mp[i][j] = mp[i - x][j - y];
}
}
}
void solve(int n){
if(n == 1){
mp[n][n] = 'X';
return;
}
solve(n - 1);
int p = power[n - 2];
draw(2 * p, 0, p);
draw(2 * p, 2 * p, p);
draw(0, 2 * p, p);
draw(p, p, p);
}
signed main(){
LOLI;
int n, T;
cin >> T;
init();
while(T --){
cin >> n;
mem(mp, ' ');
solve(n);
for(int i = 1; i <= power[n - 1]; i ++){
for(int j = 1; j <= power[n - 1]; j ++){
cout << mp[i][j];
}
cout << "\n";
}
cout << "---\n";
}
}
```
---
### 回家作業
----
#### [CF 1461D](https://codeforces.com/problemset/problem/1461/D)
可能會用到其他算法做一些優化
----
在學完DFS和回溯法之後會有更多題目
可以好好期待一下
{"metaMigratedAt":"2023-06-15T13:20:46.911Z","metaMigratedFrom":"YAML","title":"MDCPP遞迴講義","breaks":true,"image":"https://i.imgur.com/NZiHUtv.jpg","slideOptions":"{\"theme\":\"sky\",\"transition\":\"slide\"}","description":"作者：LittlePants","contributors":"[{\"id\":\"853e1517-7034-4077-803a-7bb83a49f00a\",\"add\":12429,\"del\":5051}]"}