---
# System prepended metadata

title: DS_Recursion
tags: [CYCS_DS]

---

# 遞迴

{%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$

