---
title: 遞迴 # 簡報的名稱
tags: 7th 教學 # 簡報的標籤
---
# 遞迴
#### Author: PixelCat
## 概要
1. 遞迴的架構
2. 遞迴問題複雜度分析
3. 例題們
3.1. 河內塔
3.2. 費氏數列
3.3. 快速冪
3.4. 等比級數
4. 結語
## 遞迴的架構
記得c++裡面的函數嗎？函數可以被呼叫，假如某個函數呼叫了自己，就叫做遞迴
```cpp=
void func(){
cout << "func() called\n";
func(); //recursion
}
void f1(){
cout << "f1() called\n";
f2(); //recursion?
}
void f2(){
cout << "f2() called\n";
f1(); //recursion?
}
// f1() -> f2() -> f1() -> f2() ....
// recursion indeed
```
但是執行`func()`，你發現他一直輸出，停不下來。為什麼？因為`func()`輸出一行，呼叫了（第二層）`func()`，第二層輸出完呼叫第三層，第三層呼叫第四層...沒完沒了。
像這樣不會結束的遞迴，叫做**無窮遞迴**。為了避免無窮遞迴，我們要設定一個遞迴的終止條件(或者叫base case)。
```cpp=
void func(int n){
cout << "func(" << n << ") called\n";
if(n == 0) return; // end of recursion
func(n - 1);
cout << "func(" << n << ") ended\n";
}
```
注意觀察每一層遞迴執行的順序。
## 遞迴問題複雜度分析
先來一個遞迴的例子吧。
```cpp=
int count(int n){
if(n == 0) return 0; // base case
int ans = count(n/2); // recursion
ans = ans + n % 2;
return ans;
}
```
從上面的例子可以把遞迴拆成三個部份：
1. 做事，不做事你寫程式幹嘛
2. 遞迴，不遞迴還叫遞迴嗎
3. 終止條件，不設終止條件會造成無窮遞迴停不下來
真正在花時間的是做事的部份，棘手的是這個函數可能被呼叫多次，所以要把每一次呼叫的複雜度加起來。通常我們會畫一棵「遞迴樹」來找出函數被呼叫了幾次，以上面的例子來說，呼叫`count(36)`會有這棵遞迴樹(因為count太長了所以用f代替)：
count被呼叫了七次。
假如呼叫`count(n)`呢？
每次n都變一半，直到n變0，需要 $1+\log n$ 次，時間複雜度 $O(\log n)$。
不過當然也不是所有遞迴樹都這麼和善，比如下面的例題二。
## 例題們
### 例題一：河內塔
[green judge b023 河內塔](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b023)
給你三跟柱子和n個圓盤，每個圓盤大小不同，疊在柱子上，小的不可以疊在大的下面。現在所有圓盤疊在第一根柱子上，你每次可以把某堆最上面的一個圓盤換到另外一根柱子上，要如何操作使所有圓盤疊到第三根柱子上？
green judge已經幫你破梗了，假如要把圓盤1~n從a移動到b，我們可以
1. 將圓盤1\~n-1從a移動到另一根柱子c
2. 將圓盤n從a移動到b
3. 將圓盤1\~n-1從c移動到另一根柱子b
其中，1和3是一個模式完全相同的問題，可以遞迴解決，終止條件是當 $n=0$ 時，什麼都不需要移動，直接結束回傳。
:::spoiler 參考程式碼（未經實測）
```cpp=
// move disk 1~n from a to b through c
void solve(int n,int a,int b,int c){
if(n == 0) return; // 終止條件
solve(n-1, a, c, b); //遞迴
cout << "Ring " << n <<
" from " << a <<
" to " << b << "\n";
solve(n-1, c, b, a); //遞迴
}
solve(n, 1, 3, 2);
```
:::
<br/>
每次呼叫都會呼叫兩次下一層的遞迴，直到n是0，複雜度 $O(2^n)$。
遞迴樹如下圖。
### 例題二：費氏數列
給你一個函數，也就是知名的費氏數列：
$$
fib(n) =
\begin{cases}
1, & \text{if } n\leq 2 \\
fib(n-1)+fib(n-2), & \text{otherwise} \\
\end{cases}
$$
請你求出數列的第n項。
既然都給你遞迴式了，直接寫出來就好。
```cpp=
int fib(int n){
if(n <= 2) return 1;
return fib(n-1) + fib(n-2);
}
```
他的複雜度是多少？我們可以畫出他的遞迴樹
想一想你會發現，函數總共被呼叫的次數剛好是費氏數列的前n項加起來，而根據費氏數列的一般項公式，我們知道費氏數列的第n項大概在 $O(\phi^n)$，其中 $\phi=\frac{1+\sqrt{5}}{2}=1.618\dots$是黃金比例。
因此總時間複雜度是 $O(\phi^n)$。
:::spoiler 題外話
在上面的遞迴樹中，我們看到同一項被呼叫很多次，比如`fib(3)`被呼叫3次，`fib(2)`被呼叫5次。可是`fib(3)`走到哪裡都是`fib(3)`，何必算這麼多次？
這就是動態規劃的戰場了。
:::
### 例題三：快速冪
給你正整數 $a,b,m$，請求出 $a^b\bmod m$。
$a,b\leq 10^{18}$，$m\leq 10^9$，取餘數是因為 $a^b$ 可能超級無敵大。
乍看只能做b次慢慢乘，但根據指數律我們觀察到
$$
a^b =
\begin{cases}
1, & \text{if } b=0 \\
a^k\times a^k, & \text{if } b=2k \\
a^k\times a^k \times a, & \text{if } b=2k+1
\end{cases}
$$
$a^k$ 出現了這麼多次，但是 $a^k$ 走到哪裡都還是 $a^k$，完全可以重複利用。於是我們每次遞迴都可以把 $b$ 變一半，複雜度進步成 $O(\log b)$
```cpp=
long long fpow(long long a, long long b, int m){
if(b == 0) return 1;
int ak = fpow(a, b/2, m);
if(b%2 == 0) return ak * ak % m;
else return ak * ak % m * a % m;
}
```
這個技巧很好實做，非常常用。這裡提供一種迴圈式的寫法，常數比遞迴稍小但不會差太多
:::spoiler 迴圈式快速冪實做
```cpp=
long long fpow(long long b, long long p, int mod){
long long ans = 1;
while(p){
if(p & 1)
ans = ans * b % mod;
b=b*b%mod;
p/=2;
}
return ans;
}
```
:::
### 例題四：等比級數
給你 $r,n,m$，請你求出等差級數和 $\left(1+r+r^2+\dots+r^{n-1}\right)\bmod m$。
$r,n\leq 10^{18}$，$m\leq 10^9$，取模是因為級數可能宇宙無敵大。
延續上一題的思路，我們又要來找有沒有重複的東西可以用了。
為了說明方便，我們令
$$
f(r,n)=\sum^{n-1}_{k=0}r^k\bmod m
$$
模數m在過程中不會變所以視為常數。
**++想法一，從中間分一半++**
分成 $n$ 是奇數和偶數的情況觀察，你發現
$$
f(r,2k+1) = 1+r\times f(r,2k)
$$
奇數的情況直接可以變成偶數，不理他。
$$
\begin{align}
f(r,2k) &= f(r,k)+r^k\times f(r,k) \\
&= f(r,k)\times\left(1+r^k\right)
\end{align}
$$
偶數的情況中 $f(r,k)$ 可以直接遞迴重複利用，至於 $r^k$ 可以在遞迴的時候一併計算，一次回傳兩個答案。
終止條件在遞迴到 $n=0$ 時，$f(r,n)=1$，$r^n=1$。
```cpp=
// same as #define ll long long
using ll = long long;
// pair{ f(r,n) , r^n }
pair<ll, ll> f(ll r, ll n, ll m){
if(n == 0){ // base case
return make_pair(1, 1);
}
if(n%2 == 0){ // even
auto res = f(r, n/2, m);
return make_pair(
res.first * (1 + res.second) % m,
res.second * res.second % m
);
}else{ // odd
auto res = f(r, n-1, m);
return make_pair(
(1 + r * res.first) % m,
res.second * res.second % m * r % m
);
}
}
```
其實本質上就是把一個快速冪和等比級數包在一起，複雜度 $O(\log n)$。
**++想法二，分奇偶項++**
快速冪看起來還是有點冗，能不能去掉那項 $r^k$？
奇數一樣不用管他，來看看n是偶數的情況
$$
\begin{align}
f(r,2k) &= 1+r+r^2+\dots+r^{2k-2}+r^{2k-1} \\
&= \left(1+r^2+\dots+r^{2k-2}\right)+\left(r+r^3+\dots+r^{2k-1}\right) \\
&= f(r^2,k)+rf(r^2,k)
\end{align}
$$
乾淨簡潔！
終止條件依然是在 $n=0$ 時。
```cpp=
using ll = long long;
ll f(ll r, ll n, ll m){
if(n == 0) // base case
return 1;
else if(n%2 == 1) // odd
return (1 + r * f(r, n-1, m)) % m;
else // even
return f(r*r%m, n/2, m) * (1+r) % m;
}
```
複雜度同樣是 $O(\log n)$，不過因為少了快速冪的部份所以常數小了不少。
:::spoiler 題外話
假如你學過等比級數，你可能會想到
$$
f(r,n)=\sum^{n-1}_{k=0}r^k=\frac{r^n-1}{r-1}
$$
既然 $r^k$ 可以快速冪，那問題就解決了，嗎？
不幸的是，除法在取模下是不生效的，就算你會模逆元，還是會有模逆元不存在的情況（比如說r=3,m=4，r-1和m不互質），因為題目沒有跟你保證m是質數。
所以還是乖乖遞迴吧！
:::
## 結語
這篇本來想跟分治放一起的，但是寫一寫就變超級長，想起什麼例題都想丟進去。遞迴是一個重要的概念，幾乎所有領域都有需要遞迴的時候，就連二分搜也可以視為遞迴問題的一種，因此請一定要看懂遞迴，至少要能看懂複雜度分析和例題一、二。
學習遞迴還有一個重要的目的是為分治鋪路，希望大家有學起來（也希望我寫出來的東西是人話）！
Sign in with Wallet
Connect another wallet