# 遞迴
函式自己呼叫自己，並存放於stack中(因為是先進後出)

## 費氏數列
$$f(n)= \begin{cases}
f(n-1)+f(n-2) & n\geq3\\
\quad\quad\quad\quad 1 & n=1,2
\end{cases}$$

寫成遞迴式

int f(int n){
    if(n<=2) return 1;
    return f(n-1)+f(n-2);
}

### 優化
我們可以由上式推得:
$$ f(n)=\frac{(\frac{\sqrt{5}+1}{2})^n-{(\frac{\sqrt{5}-1}{2})^n}}{\sqrt{5}} $$

那麼這個遞迴式的複雜度為$O(2^n)$，再觀察遞迴樹:


發現一個函式可能被呼叫多次，那麼如果把執行過一次的函式記錄起來，下次呼叫就可以$O(1)$回答，此時複雜度為$O(n)$

vector<int> fib(100000);
int f(int n){
    if(fib[n]) return fib[n]; 
    if(n<=2) fib[n]=1;
    else fib[n]=f(n-1)+f(n-2);
    return fib[n];
}

另外，減少參數的數量(如使用全域變數)可以提升效率

### 補充:矩陣優化

#### 快速冪
欲求$x^n$，暴力乘一遍，$O(n)$
若把$n$拆為2的次方，ex: $x^{11}=x^8 \times x^2 \times x^1$
事先求出$x^1,x^2,x^4...$只需$O(logn)$(一直平方到超過n就好了)
又$n$可由2的次方組合而成(並且總數不超過$log_2n$)，所以複雜度可達$O(logn)$

為求簡潔，一邊求$x^{2^n}$一邊組合可寫成:

int muti(int x,int n){
    int ans=1;
    while(n>0){
        if(k%2) ans*=x;
        x*=x;
        n>>=1;
    }
    return ans;
}

#### 矩陣
一個$2 \times 3$的矩陣A表示如下:
$$A=
\begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3}\\ a_{2,1} & a_{2,2} &a_{2,3} \end{bmatrix}$$

若A為 $x \times y$ 的矩陣，B為 $y \times z$ 的矩陣，則定 $A \times B$ 為 $x \times z$ 的矩陣C表示如下:
$$c_{i,j}=\sum_{k=1}^ya_{i,k}+b_{k,j}$$

#### 費氏數列

因為$fib(n)=fib(n-1)+fib(n-2)$，所以可得

$$
\begin{bmatrix} fib(n-1) & fib(n-2) \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 1 & 0\end{bmatrix}=
\begin{bmatrix} fib(n) & fib(n-1) \end{bmatrix}$$

推成一般式:

$$
\begin{bmatrix} 1 & 1 \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 1 & 0\end{bmatrix}^{n-2}=
\begin{bmatrix} fib(n) & fib(n-1) \end{bmatrix}$$

因為矩陣乘法有結合率，所以可以用快速冪!
這樣一來求$fib(n)$的複雜度就是$O(logn)$

## 剪枝
遞迴可以模擬所有情況，再從中找出(或枚舉出)答案，但是對於已經不可能是答案的情況，就不用繼續遞迴下去

### 括號匹配問題
[zj:a229](https://zerojudge.tw/ShowProblem?problemid=a229)

列出合法的括號(左邊一個配右邊一個)，$n=$括號組數$\leq13$
#### 題解
考慮暴力遞迴，每次選左和選右，如果長度$=2n$就停止，檢查是否合法，複雜度$O(2^{2n})$，且$n\leq13$，最多會執行$10^{7.8}$次，顯然過不了。
那麼有什麼情況下可以提前終止呢?如果一種括號已經超過n個，那麼顯然不可能成對:又如果右括號出現的比較多次也不可能合法。


[圖源:上一屆的講義](https://hackmd.io/@niter/ryhPGrsBs)

### Grid Paths
[cses:Grid Paths](https://cses.fi/problemset/task/1625/)

從左上到左下走滿7*7方格


因為總步數恆等於48，所以走到48步時檢查是否在左下方格就可以得知是不是解

#### 剪枝1
顯然，如果走到已經走過的格子就可以不用走了

#### 剪枝2
撞到牆也可以不用走了

#### 剪枝3
如果提早走到終點也不可能是解

剪到這邊發現還是TLE，只好繼續剪...

#### 剪枝4
如果前面是牆，左右都沒走過，那麼左右一定有一個走不到(地圖被分成兩半)

#### 剪枝5
如果右上有走過，而上和右都沒走過，那麼上右一定有一個走不到(有一個被包圍了)，轉向後同理，可以剪四種

至此，我們知道了剪枝後的複雜度很難算(至少我算不出來)，但是肯定比原本快。如果還是TLE的話代表剪不夠，還有你沒想到的情況可以剪