# 遞迴
`第12週社課`
## 定義
函式自己呼叫自己，
呼叫下一個函式時，原本的函式狀態會被儲存在記憶體的stack空間中，
被呼叫的函式結束後，才會從stack取出目前的狀態，因此還是單執行緒。
(要寫多執行緒沒這麼簡單！)
### 為什麼是stack？
因為遞迴滿足後呼叫的函式先結束，也就是先取出。

## 終止條件
就跟數學中的遞迴一樣，程式中的遞迴必須有終止條件(base case)，
否則會變成無限遞迴，然後就會stack overflow(也可以說是爆記憶體)。
::: spoiler 實驗
這個code可以在一瞬間製造stack overflow的情況，然後程式就會crash掉，
如果想要觀察得更清楚一點，可以把第7行的for迴圈取消註解，
然後打開工作管理員來觀察程式的記憶體使用量。

#include <bits/stdc++.h>
using namespace std;

int f(); int g();

int f(){
    //for(int i = 1; i <= 1000000; i++);
    return g();
}

int g(){
    return f();
}

int main(){
    f();
}

:::
<a> </a>
例如：計算費氏數列時，終止條件為$n=1$或$n=2$，算到這個的時候就可以不用再遞迴下去了。
下面的數學式即為費氏數列的遞迴式。
$$
F_n=\left\{
\begin{aligned}
{1\quad \quad }\quad {n = 1}\\
1\quad \quad \quad {n = 2}\\
F_{n-1} + F_{n-2}\quad {n \geq 3}
\end{aligned}
\right.
$$
下面的程式可以用來計算費氏數列，寫法幾乎跟上面的式子一樣。

#include <bits/stdc++.h>
using namespace std;

int F(int n){
    if(n == 1 || n == 2)
        return 1;
    return F(n-1) + F(n-2);
}

int main(){
    cout << F(5) << "\n";
}

如果還不熟悉遞迴，可以先在紙上列出遞迴式，再開始寫程式碼。

## 另一個範例

GCD(最大公因數)
$$
gcd(a,b)=\left\{
\begin{aligned}
gcd(b,a)\quad\,{a<b}\\
b \quad\quad\;\;{r=0}\\
gcd(b,r)\quad{r\neq0}\\
\end{aligned}
\right.
\,\,\,\,(r為a~÷~b所得的餘數)
$$

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b){
    if(b > a) return gcd(b ,a);
    int r = a % b;
    return (r == 0) ? b : gcd(b, r);
}

int main(){
    cout << gcd(21,6); // 3
}

## 圖解

#include <bits/stdc++.h>
using namespace std;

int F(int n){
    if(n == 1 || n == 2)
        return 1;
    return F(n-1) + F(n-2);
}

int main(){
    cout << F(5) << "\n";
}

以費氏數列來舉例，最初被呼叫的函式就是樹的根，新呼叫的函式可以被視為樹的分支。
對比程式碼與下圖，每個分支點是先呼叫左分支，回傳之後再呼叫右分支。
順帶一提，這張圖又被稱為遞迴樹。
$$ \\
$$

debug時，可以邊遞迴邊紀錄遞迴的層數，
在輸出時以空格數來表示層數，就可以看出是誰呼叫誰。</br>
Code:

#include <bits/stdc++.h>
using namespace std;

int F(int n, int layer){
    for(int i = 0; i < layer; i++){
        cout << "    ";
    }
    cout << "F(" << n << ")\n";
    if(n == 1 || n == 2)
        return 1;

    return F(n-1, layer + 1) + F(n-2, layer + 1);
}

int main(){
    F(5,0);
}

輸出：

F(5)
    F(4)
        F(3)
            F(2)
            F(1)
        F(2)
    F(3)
        F(2)
        F(1)


## 優化
### 複雜度優化
如果用上面的程式來計算$F(50)$？(記得把int改成long long)
欸？算不出來？

如果照上面的寫法，計算$F(50)$時總共要計算幾次$F(3)$？

又沒有可能把次數壓到一次？

::: spoiler 解答
紀錄所有算過的狀態的答案！

對於費氏數列，我們可以用一維陣列(其他的可能需要更多維)來實現，
儲存一次該狀態的答案後，下次再呼叫該狀態，就可以直接回傳該陣列的值！

#include <bits/stdc++.h>
using namespace std;

vector<long long> ans;

long long F(int n){
    if(ans[n] != -1) return ans[n];
    ans[n] = F(n-1) + F(n-2);
    return ans[n];
}

int main(){
    ans.resize(100, -1);
    ans[1] = 1;
    ans[2] = 1;
    cout << F(50) << "\n";
}

此時的複雜度從$\large O(2^n)$（其實是$\large O(1.618^n)$）變成了$\large O(n)$
這個技巧被稱為***Memoization***，之後教DP時會再次提到。

:::

### 常數優化
減少遞迴函式的參數個數，可以提升執行效率。
直接舉例：<a href="https://zerojudge.tw/ShowProblem?problemid=d304">ZJ d304</a>
::: spoiler AC code

#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define pb push_back
using namespace std;
int a[10000],n,ways,press,ans_i;
vector<int> ans;

void sim(int cnt,int cp,int i){
    if(cnt>n||i>press){
        return;
    }
    else if(cnt==n){
        if(cnt!=cp){
            if(press>i){
                press=i;
                ways=0;
                ans.clear();
            }
            if(i==press){
                ans.pb(0); //c=>-1 v=>N end=>0
                loop(j,1,i) ans.pb(a[j]);
            }
            ways++;
            return;
        }
    }
    //Ctrl C
    if(cnt!=cp){
        a[i]=-1;
        sim(cnt,cnt,i+1);
        a[i]=0;
    }
    //Ctrl V
    a[i]=1;
    sim(cnt+cp,cp,i+1);
    a[i]=0;

    return;
}

int main(){
    while(scanf("%d",&n)!=EOF){
        ans.clear();
        ways=0; press=10000; ans_i=0;
        sim(1,1,1);
        printf("min : %d\nway : %d\n",press,ways);

        loop(i,0,ans.size()){
            if(ans[i]==0){
                if(i>0) printf("\n");
                printf("Ctrl C");
            }
            else if(ans[i]==-1) printf(" + C");
            else printf(" + V");
        }
        printf("\n");
    }
    return 0;
}

:::

::: spoiler TLE code

#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define pb push_back
using namespace std;
int a[1000],n,ways,press,ans_i;
vector<int> ans;

void sim(bool cmd,int cnt,int cp,int i,int p){
    if(cnt>n||p>press){
        return;
    }
    else if(cnt==n){
        if(!cmd){
            if(press>p){
                press=p;
                ways=0;
                ans_i=ans.size();
            }
            if(p==press){
                ans.pb(0); //c=>-1 v=>N end=>0
                loop(j,1,i+1) ans.pb(a[j]);
            }
            ways++;
            return;
        }
    }
    else if(cmd){
        a[i]=-1;
        sim(false,cnt,cnt,i+1,p+1);
        a[i]=0;
    }
    else{
        a[i]++;
        cnt+=cp;
        sim(true,cnt,cp,i+1,p+1);
        sim(false,cnt,cp,i,p+1);
        a[i]=0;
    }
}

int main(){
    while(scanf("%d",&n)!=EOF){
        ways=0; press=10000; ans_i=0;
        sim(true,1,0,0,0);
        printf("min : %d\nway : %d\n",press,ways);
        loop(i,ans_i,ans.size()){
            if(ans[i]==0){
                if(i>ans_i) printf("\n");
                printf("Ctrl C");
            }
            if(ans[i]==-1) printf(" + C");
            else loop(j,0,ans[i]) printf(" + V");
        }
        printf("\n");
    }
    return 0;
}

:::
不過要注意，不要過度依賴全域變數，不一定會比較快。
重點是減少不必要的參數「傳遞」。
確實，如果把上面的星星數換成全域會直接TLE掉(實際測過)

<!-- TO DO -->

## 應用
### 依遞迴式求出單一狀態
優點：想法直接
範例：費氏數列，不再贅述
### 模擬所有情況
<!-- 遞迴為什麼適合用來模擬所有組合？ -->
遞迴之所以適合用來模擬所有情況是因為：
他可以用一個狀態來表達一層重複結構。
例如：今天我想要得到一個集合所有的子集合的和，最直接也是最簡單的方法就是用n個for迴圈包他，但是顯然這個方法實作下來很不實際，所以遞迴就會派上用場了，我們可以用多層遞迴來取代多層for迴圈。(如果你要寫不確定幾層的for迴圈，用遞迴就對了)
來看看code。

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 22;

int n, k = 0, element[MAX_N], subset_sum[1 << MAX_N];
bitset<MAX_N> state;
// 用bitset儲存一個「狀態」，雖然可以用一個int進行
// 狀態壓縮，但那會變得比較抽象，所以先不教

int get_sum() {
	int i, result = 0;
	for (i = 0; i < n; ++i) {
		if (state[i]) {
			result += element[i];
		}
	}
	return result;
}

void enum_state(int pos) {
	if (pos == n) {
		subset_sum[k++] = get_sum();
		return;
	}
	state[pos] = 0;
	enum_state(pos + 1);
	state[pos] = 1;
	enum_state(pos + 1);
}

int main() {
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> element[i];
	enum_state(0);
	sort(subset_sum, subset_sum + k);
	for (int i = 0; i < k; ++i) cout << subset_sum[i] << ' ';
}

執行結果：
複雜度：$O(n\times 2^n)$
因為我們模擬了所有$2^n$種狀態，輸出時$O(n)$計算該狀態的值。

::: spoiler 優化
其實有方法可以把那個$\large O(n)$去掉，就是把目前取到的總和當作參數傳遞下去。

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 22;

int n, k = 0, element[MAX_N], subset_sum[1 << MAX_N];

void enum_state(int pos, int now) {
	if (pos == n) {
		subset_sum[k++] = now;
		return;
	}
	enum_state(pos + 1, now);
	enum_state(pos + 1, now + element[pos]);
	return;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> element[i];
	enum_state(0, 0);
	sort(subset_sum, subset_sum + k);
	for (int i = 0; i < k; ++i) cout << subset_sum[i] << ' ';
}

:::

## 剪枝

對於一個不可能成為解的路線後面全部不要去訪問。

例如：最經典的括號匹配問題

可以先從手算的情況開始想，通常我們都會畫樹狀圖來表達分支，
如果這個分支不可能是解，那麼它的分支也不會是解，所以可以直接把它劃掉。

* 遞迴目標：一個位置的左括號或右括號
* 不可能成為解的情形：左括號或右括號個數大於總括號組數、右括號個數大於左括號個數

題外話：如果你在剪枝的時候需要debug然後在遞迴裡面印狀態發現怎麼code變很慢，有的時候不要怕，你已經剪對了，只是I/O慢爆了

### 下次課程：分治法
將原本的問題拆成多個子問題分開計算，再把這些子問題的答案合併成大問題的答案。
會這樣做是因為拆解再合併的複雜度較優，如果沒有比較好，則應該嘗試別的方法。