# 遞迴
----
遞迴是指在函式中直接或間接的呼叫自己，
以達到重複執行的目的。
---
# 基礎遞迴架構
----
首先，要知道怎麼遞迴。
再來，列出終止條件。
最後，把遞迴式放入程式。
---
## 例題 河內塔([ZJ i322](https://zerojudge.tw/ShowProblem?problemid=i322))
有三個柱子與n個環，從小到大
由上而下堆在柱子A上。
我們想要把所有的環都搬到柱子C上，
但是過程中，大環不能在小環上面。
----
## 遞迴式
假設我們要把前i個環從柱子x搬到柱子y
首先，我們要先把上面的環都從柱子x搬到柱子z
接著，把第i個環搬到柱子y
最後，把原本上面的環從柱子z搬到柱子y
----
```cpp=
#include <bits/stdc++.h>
using namespace std;
void hanoi(int l, char c1, char c2, char c3){
//l:第幾個環 c1:從哪裡, c2:到哪裡, c3:剩下那個
if(l==0) return;
hanoi(l-1, c1, c3, c2); //先把上面的都搬到剩下那個
cout << "Move disc " << l << " from " << c1
<< " to " << c2 << '\n'; // 這個環搬到目標處
hanoi(l-1, c3, c2, c1); //再把上面的從剩下那邊搬到目標處
}
int main()
{
int n;
cin >> n;
hanoi(n, 'A', 'C', 'B'); //從A搬到C，共n層
return 0;
}
```
---
# 改善遞迴
我們可以透過一些方法減少遞迴需要的時間
----
## 例題 費氏數列([ZJ e794](https://zerojudge.tw/ShowProblem?problemid=e794))
費氏數列的前兩項都是1，而後面每一項
都是前兩項的和。
----
## 遞迴式
${fib}_0=1$
${fib}_1=1$
${fib}_n = {fib}_{n-1} + {fib}_{n-2},\ n \ge 2$
要輸出${fib}_{n-1}和{fib}_n$
----
## 例題解答
```cpp=
#include <bits/stdc++.h>
using namespace std;
long long fib(int n){
if(n<0) return 0; // 以免發生輸入錯誤
if(n==1 || n==0) return 1; // 停止條件
return fib(n-1)+fib(n-2); // 遞迴式
}
int main(){
int n;
cin >> n;
cout << fib(n-1) << ":" << fib(n) << '\n';
return 0;
}
```
----
但是這個方法時間會花很久(會TLE)。
這是因為我們會重複算同樣的東西好多次。
因此我們需要改善這個方法。
---
## 改善1 - 儲存算過的值
我們可以發現，有不少的值會一直被重複呼叫。
因此，我們可以把算過的存起來，不要重複計算。
----
## 改善程式1
```cpp=
#include <bits/stdc++.h>
using namespace std;
long long fi[5001]; //先宣告最大需求的陣列
long long fib(int n){
if(n<0) return 0; // 以免發生輸入錯誤
if(fi[n]) return fi[n];
// 停止條件改為遇到有值的(0和1已經是1)
fi[n] = fib(n-1) + fib(n-2); // 遞迴式
return fi[n];
}
int main(){
int n;
fi[0] = 1; // 初始條件
fi[1] = 1;
cin >> n;
cout << fib(n-1) << ":" << fib(n) << '\n';
return 0;
}
```
---
## 改良2 - 迴圈化
我們有時候可以把這個遞迴式變成迴圈，
因為迴圈不用跳到不同層，執行上比較快，
而且也不用擔心堆疊溢位的問題。
雖然這樣已經不算是遞迴了，但是它
還是用遞迴式推出來的。
----
我們現在知道只要我們有${fib}_{n-1}$和${fib}_{n-2}$，
我們就可以算出${fib}_{n}$，
因此我們可以從下往上算。
----
## 改善程式2
```cpp=
#include <bits/stdc++.h>
using namespace std;
long long fi[5001]; //先宣告最大需求的陣列
int main(){
int n;
fi[0] = 1; //初始條件
fi[1] = 1;
cin >> n;
for(int i=2; i<=n; i++){
fi[i] = fi[i-1] + fi[i-2]; // 遞迴式
}
cout << fi[n-1] << ":" << fi[n] << '\n';
return 0;
}
```
---
## 改良3 - 縮減儲存
有時候我們甚至可以不用存所有的值，
只要存我們會用到的就好。
因為有時候要存的陣列太大，可能會出問題。
或是為了避免MLE(記憶體不夠)。
----
在費氏數列，我們只需要知道最後兩項，就可以推出下一項。
因此我們只要存兩項就好。
----
## 改善程式3
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
long long prev1 = 1, prev2 = 1, next; // 只要知道前兩個就好。
cin >> n;
for(int i=2; i<=n; i++){
next = prev1 + prev2; // 遞迴式
prev1 = prev2; // 存新的｢最後兩個｣
prev2 = next;
}
cout << prev1 << ":" << prev2 << '\n';
return 0;
}
```
---
## 改良方法2 - 提前停止
有時候，我們用遞迴來窮舉方法。
這時，如果可以在跑到停止條件前，
先知道這個後面的都不可行的話，
那麼就可以直接退出，不用繼續跑下去。
---
# 總結
步驟1: 列出遞迴式
步驟2: 寫出遞迴程式
步驟3: 修正、改良
---
# 推薦題目
[ZJ f928](https://zerojudge.tw/ShowProblem?problemid=f928)
[ZJ i644](https://zerojudge.tw/ShowProblem?problemid=i644)
[ZJ d443](https://zerojudge.tw/ShowProblem?problemid=d443)
{"title":"遞迴","contributors":"[{\"id\":\"00ad9127-6491-4b3d-829b-7847a217f8e5\",\"add\":6107,\"del\":2875}]","description":"遞迴是指在函式中直接或間接的呼叫自己，以達到重複執行的目的"}