# 遞迴
{%hackmd theme-dark %}
:::info
Def:
遞迴是將大問題分成許多小問題來解決問題的方式，在Programming上，若一函式呼叫他自己，稱該函式為遞迴函式
:::
## 二分搜
在**已排序**的一堆資料中以Divide & Conquer(分治)理念找到想要的答案
#### Iterative:
```cpp
int l = 0, r = n-1; // 設定左右邊界
while(l<r){
int mid = l+(r-l)/2; // 設定中間點，把 (l+r)/2 改成這樣可以避免 overflow
if(中間點的值比目標還大){
l = mid+1; // 答案在右邊，左半邊不用看了
}else{
r = mid; // 答案在左邊，右半邊不用看了
}
}
```
#### Recursive:
```cpp
int BinarySearch(int arr[], int target, int l, int r) {
if (l == r) // 找到最接近的
return l;
int mid = l + ((r - l) >> 1); // (l+r)/2
if (arr[mid] >= target) // target比mid小，答案在左半邊
return BinarySearch(arr, target, l, mid);
else // target比mid大，答案在右半邊
return BinarySearch(arr, target, mid + 1, r);
}
```
## 遞迴使用時機
- 已知邊界(終止)條件
- 可拆分成更小但相同的問題
## 階乘
#### Iterative:
$$ f(n) = n! =
\begin{cases}
n \times (n-1) \times (n-2) \times \dots \times 1 & n>0 \\
1 & n = 0
\end{cases}
$$
#### Recursive:
$$ f(n) = n! =
\begin{cases}
n \times f(n-1) & n>0 \\
1 & n = 0
\end{cases}
$$
```cpp
Integer Factorial(Integer n){
if(!n) return 1;
return n * Factorial(n-1);
}
```
## Box trace
用於幫助了解遞迴運作方式，至少包含：
- 輸入參數、區域變數
- 遞迴呼叫得到的值
- 自己要回傳的值
```mermaid
graph LR;
func("F(n)") --> 3("n = 3<br>
A:F(n-1) = 2<br>
return 6")
3 --> 2("n = 2<br>
A:F(n-1) = 1<br>
return 2")
2 --> 1("n = 1<br>
A:F(n-1) = 1<br>
return 1")
1 --> 0("n = 0<br>
return 1")
style func fill: #ffffff, stroke: #ffffff ;
```
## 字串反轉
```cpp
void WriteBackward(string s) {
if (!s.empty()) {
cout << s.back();
s.pop_back();
WriteBackward(s);
}
}
```
```cpp
void WriteBackward2(string s) {
if (!s.empty()) {
WriteBackward(s.substr(1));
cout << s[0];
}
}
```
## 找最大值
```cpp
int FindMax(int arr[], int l, int r) {
if (l == r)
return arr[l];
int mid = (l + r) >> 1;
int left = FindMax(arr, l, mid);
int right = FindMax(arr, mid + 1, r);
return max(left, right);
}
```
### 另解(RMQ Problem)
#### Segment tree
```cpp
struct Node {
Node *l, *r;
int val;
};
Node *build(Node *&root, int l, int r, int *arr) {
if (root == NULL) {
root = new Node();
}
if (l == r) {
root->val = arr[l];
return root;
}
int mid = (l + r) >> 1;
root->l = build(root->l, l, mid, arr);
root->r = build(root->r, mid + 1, r, arr);
root->val = max(root->l->val, root->r->val);
return root;
}
int query(Node *root, int l, int r, int ql, int qr) {
if (l > qr || r < ql)
return 0;
if (l >= ql && r <= qr)
return root->val;
int mid = (l + r) >> 1;
return max(query(root->l, l, mid, ql, qr),
query(root->r, mid + 1, r, ql, qr));
}
```
## 線性遞迴
### 基底條件
* 至少要有一種基底條件
* 所有遞迴呼叫最終都必須趨向基底條件
* 處理基底條件不應使用遞迴
### 遞迴次數
* 只呼叫一次
* 可決定如何呼叫，但只能呼叫一次
* 必須趨向基底條件
### 找第K小值
#### Quick Select:
```cpp
int FindKthLargest(int *arr, int k, int l, int r) {
int pivot = arr[r];
int i = l - 1;
for (int j = l; j < r; j++) {
if (arr[j] > pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[r]);
if (i + 1 == k - 1)
return arr[i + 1];
else if (i + 1 > k - 1)
return FindKthLargest(arr, k, l, i);
else
return FindKthLargest(arr, k, i + 2, r);
}
```
#### 一般Segment Tree:
葉節點紀錄對應數組(node[i] = arr[i])
#### 權值Segment Tree:
葉節點紀錄數組去重後第i小的出現次數(node[i] = Count(arr[i]))
```cpp
int query(int l, int r, int id, int k) {
if(l == r)
{
return l;
}
int mid = (l + r) >> 1;
if(k <= cnt[id << 1])
query(l, mid, id << 1, k);
else query(mid + 1, r, id << 1 | 1, k - cnt[id << 1]);
}
```
### 反轉陣列
```cpp
void ReverseArray(int *arr, int l, int r){
if(l < r){
swap(arr[l], arr[r]);
ReverseArray(arr, l+1, r-1);
}
}
```
### 河內塔
```cpp
void Hanoi(int count, int source, int destination, int spare){
if(count == 1){
cout << "Move a disk from " << source << " to " << destination << '\n';
return;
}
Hanoi(count-1, source, spare, destination);
Hanoi(1, source, destination, spare);
Hanoi(count-1, spare, destination, source);
}
```
## 二元遞迴
* 只要不是基底條件就呼叫兩次遞迴
### 畫尺的標線
```cpp
void drawRuler(int n, int len){
drawOneTick(len, 0);
for(int i=1;i<=n;++i){
drawTicks(len-1);
drawOneTick(len, 1);
}
}
void drawTicks(int len){
if(len>0){
drawTicks(len-1);
drawOneTick(len, -1);
drawTicks(len-1);
}
}
void drawOneTick(int len, int tag){
for(int i=0;i<len;++i)
cout << "-";
if(tag>=0)
cout << " " << tag;
cout << '\n';
}
```
### 費波那契數列
$O(2^n)$
```cpp
int fib(int n){
if(n<=2) return 1;
return fib(n-1) + fib(n-2);
}
```
#### 線性遞迴版
$O(n)$
```cpp
pair<int,int> fib(int k){ // return {fib(k), fib(k-1)}
if(k==1) return {k, 0};
pair<int,int> r = fib(k-1);
return {r.first + r.second, r.first};
}
```
### 快速冪
```cpp
#define ll long long
ll fast_pow(ll a, ll n){
if(!n) return 1;
if(n&1) return fast_pow(a,n-1) * a;
else {
ll r = fast_pow(a,n/2);
return r * r;
}
}
ll fast_pow2(ll a, ll n){
ll ret = 1;
while(n){
if(n&1) ret *= a;
n >>= 1;
a *= a;
}
return ret;
}
```
## 阿克曼函數
$$
Acker(m, n) =
\begin{cases}
n+1 & m = 0 \\
Acker(m-1,1) & n = 0 \\
Acker(m-1,Acker(m,n-1)) & otherwise
\end{cases}
$$
## 組合計數
$C^n_k = C^{n-1}_{k-1} + C^{n-1}_k$
Sign in with Wallet
Connect another wallet