---
# System prepended metadata

title: C語言：遞迴呼叫
tags: [NCKU Linux Kernel Internals, ' C語言']

---

---
tags: NCKU Linux Kernel Internals, C語言
---

# C語言：遞迴呼叫

[你所不知道的C語言：遞迴呼叫篇](https://hackmd.io/@sysprog/c-recursion?type=view)
## 從簡單的題目思考遞迴

思考以下題目: 假設有一個只含 0 / 1 的數列，要計算有多少的 0 前面是 1 的配對。以 {1,0,1,0,0,1} 為例，第一個 0 前面(左邊)有 1 個 1，第二個 0 前面有 2 個 1，第三個 0 前面有 2 個 1，所以應該要輸出 `1 + 2 + 2 = 5`。

### 解法 1
最直觀的想法是，迴圈找 0，然後去算 0 前面有幾個 1
```c=
int find(char *a,int n){
    int ans,i;
    for (i = 0, ans = 0 ; i < n ;i++) {
        if (a[i] == 0) {
            int j;
            int before = 0;
            for(j = 0; j < i; j++){
                if (a[j] == 1)
                    before ++;
            }
            ans += before;
        }
    }
    return ans;
}
```
這個作法的時間複雜度是 O(n^2)
### 解法 2
可以利用 prefix 的思維: 對於每次找到的 0，其前面的 1 是數量累積起來的。
```c=
int find(char *a,int n){
    int ans,cnt,i;
    for (i = 0, cnt = 0, ans = 0 ; i < n ;i++) {
        if (a[i] == 0) 
            ans += cnt;
        else cnt++;
    }
    return ans;
}
```
如此一來，便可以將時間複雜度降低至 O(n)

### 解法 3
轉換一下思維，讓我們用 divide and conquer 來解決此問題。如果把數列從中間切開分成左右，對於右邊的 y 個 0，左邊都各自有 x 個 1，則答案會有 x * y 個。然後再對左右的數列各自遞迴求解，詳細的程式碼如下:
```c=
int find(char *a, int left, int right) { 
    if (right - left < 2) return 0;
    int mid = (left + right) / 2; 
    int w = dc(a,left, mid) + dc(a,mid, right);
        
    int x,y;
    x = y = 0;
    // 計算左邊幾個 1
    for(int i = left; i < mid ; i++)
        if( a[i] == 1)
            x++;
    // 計算右邊幾個 0       
    for(int i = mid; i < right ; i++)
        if( a[i] == 0)
            y++;
                
    return w + x * y;
}
```
然而，這個演算法的時間 T(n) = 2T(n/2) + O(n)，得出時間複雜度為 O(n lgn)。
### 解法 4
解法 3 並不比解法 2 還要快，原因是因為我們對於 0/1 的數量重複計算，如果把程式改寫:
```c=
struct ret{
    int ans;
    int y; // 0 的數量
    int x; // 1 的數量
};

struct ret dc(char *a, int left, int right) {  
      if (right - left < 2) {
          if(a[left] == 0)
            return (struct ret){0,1,0};
          else
            return (struct ret){0,0,1};
      }
      int mid = (left + right) / 2; 
    
      struct ret w1 = dc(a,left, mid);
      struct ret w2 = dc(a,mid, right);
      
      return (struct ret){w1.ans + w2.ans + w1.x * w2.y, w1.y + w2.y, w1.x + w2.x};
}
```
則時間是 T(n) = 2T(n/2) + O(1)，時間複雜度是 O(n)。

### 總結
事實上，一個演算法的遞迴版本勢必會有對應的迴圈版本。以此題來看，看似遞迴的算法更難理解，然而如果把問題推廣到不只有 0 / 1 的數列呢(逆序數問題) ? 如果我們想要透過迴圈解題，可能會需要一個複雜的資料結構。但是如果透過遞迴，問題得以被簡單化(準確的說，使用更少的變數維護狀態，程式也更容易被理解)

對於逆序數的問題，其暴力解為:

```c=
int brute_check(int *a, int left ,int right){
    int cnt = 0;
    for(int i = left; i < right; i++){
        for (int j = left; j < i; j++){
                if(a[j] > a[i])
                    cnt++;
        }
    }
    return cnt;
}
```

但是我們可以其實可以透過遞迴求解，而其解法其實只是 merge sort 的延伸:
``` c=
int merge(int *a, int left, int mid, int right){
    int ans = 0;
    int *tmp = malloc(sizeof(int)*(right - left));
    
    int i = left;
    int j = mid;
    int k = 0;
	
    while(i < mid  && j < right)
    {
        if(a[i] <= a[j])
            tmp[k++] = a[i++];
        else
        {
            tmp[k++] = a[j++];
            ans += mid-i;
        }
    }
	
    while(i < mid )
        tmp[k++] = a[i++];
    while(j < right)
        tmp[k++] = a[j++];
		

    int count = 0;
    for(int i = left;i < right; i++)
        a[i] = tmp[count++];
    
    free(tmp);
    return ans;
}


int mergesort(int *a, int left, int right) {  
    if(right - left > 1)
    {
        int mid=(left+right)/2;
        int w = mergesort(a,left,mid) + mergesort(a,mid,right);
        int c = merge(a,left,mid,right);
        return w + c;
    }
    else
        return 0;
}
```
:::info
1. 詳細請直接參閱 [你所不知道的C語言：遞迴呼叫篇](https://hackmd.io/@sysprog/c-recursion?type=view)，此處僅附上自己額外補充的程式!
2. 本人程式 sence 極差，如果找到程式執行的問題還請告知! 大家還請多多包容qq
:::
## 迷思: 迴圈 always 優於遞迴
前面有提及，所有可以用遞迴呈現的演算法都必定有迴圈的版本。而以往我們常常有相同類型的程式，迴圈的執行速度比遞迴快的迷思(額外的 allocate / push / pop stack frame)。這個想法固然沒錯，然而，得益於編譯器越來越強大，有些時候迴圈或者遞迴版本的程式，編譯器都可以直接幫我們優化成相同的 assembly。也就是說，寫成遞迴或者迴圈的形式在執行速度並無反別，然而遞迴程式反而可能會擁有更佳的可讀性! ~~compiler 萬歲~~

該如何寫遞迴，才可以使編譯器幫我們做到最佳化呢? 這裡就必須提到 Tail recursion。Tail recursion 是遞迴的一種特殊形式，指 function 的最後一步是呼叫自己。

遞迴之所以跑得慢，是因為大量使用 stack 來儲存某些資料，如果 function 的最後一步不僅是呼叫自己，則不斷遞迴的過程中，有許多變數/ return address 都需要額外的 stack。反過來說，如果 function 的最後一步是遞迴呼叫的話，從編譯器的角度來說，遞迴實際上是不需要不斷的 call stack 的，因此便可以被優化!


Reference:
* [遞迴的美麗與哀愁](https://www.ithome.com.tw/node/81087)
* [一般递归与尾递归(Tail Recursion)](http://qiusli.github.io/blog/2013/07/09/tail-recursion/)
* [浅谈尾递归](https://site.douban.com/196781/widget/notes/12161495/note/262014367/)


## 案例分析：數列輸出
思考以下程式的功能:

```c=
int p(int i, int N) {
    return (i < N && printf("%d\n", i) && !p(i + 1, N))
           || printf("%d\n", i);
}
```

運行的關鍵在 `&&` 和 `||` 的特性。
* `A && B`: 如果 A statement 不成立，則 B 不會執行
* `A || B`: 如果 A statement 成立，則 B 不會執行

以及 [printf](https://linux.die.net/man/3/printf) 的回傳值是印出的字元數量，因此正常狀況下 p 裡的 printf 回傳不為 0。

因此，上面的程式其實等價於寫成:
```c=
int p(int i, int N) {
    if (i < N){
        printf("%d\n", i);
        p(i + 1, N);
        printf("%d\n", i);
    }
    else{
        printf("%d\n", i);
    }
}
```

## 案例分析：字串反轉
思考以下問題: 實做 char *reverse(char *s)，反轉 NULL 結尾的字串，限定 in-place 與遞迴。

解題的思路是: 如果要 in-place 完成 reverse，只要透過數個 swap 就可以了。而提到 in-place 的 swap 勢必會想到 [XOR](https://hackmd.io/9tGfpJtLTwyyOzDvlyJS2w?view#XOR-Swap)。
```c=
void swap(char *a, char *b) {
    *a = *a ^ *b; *b = *a ^ *b; *a = *a ^ *b;
}
```

有了 in-place 的 swap，就可以設計反轉字串的函式了。一個設計的思考模式是，對於一個字串 s，如果 reverse(s) 代表反轉 s，舉例反轉 `54321` 來說其實可以拆解成:
* reverse(s + 1): 先反轉後面的字串 -> **51234**
* 將 s 的 0 位置和 1 位置交換 -> **15234**
* reverse(s + 2): 把 1 位置後的字串恢復成原本的順序 -> **15432**
* reverse(s + 1): 位置 0 已經是正確的值了，此時再去反轉後面即可，字串的 0、1、... 會依序變成正確的數值，一直遞迴下去直到 '\0'

程式可以被寫成:
```c=
void reverse(char *s) {
    if((*s == '\0') || (*(s + 1) == '\0'))
        return;
        
    reverse(s + 1);
    swap(s, (s + 1));
    
    if (*(s + 2) != '\0')
        reverse(s + 2);
    
    reverse(s + 1);
}
```
然而，這個演算的時間複雜度為 O(n^2) (對於長度為 n 的字串，每次只把第 0 個放好，然而再用同樣的方法去轉剩下 n - 1 個)

但是其實我們可以轉換一下思維，假如我們先計算出字串的長度的話，其實 reverse 長度 n 的字串就是把 0 <-> n-1 / 1 <-> n-2 ......依序 swap 而已，因此:
```c=
int reverse(char *head, int idx) {
    if (head[idx] != '\0') {
        int end = reverse(head, idx + 1);
        if (idx > end / 2)
            swap(head + idx, head + end - idx);
        return end;
    }
    return idx - 1;
}
```
其實只要遞迴求長度，然後透過長度計算要交換的對應位置在哪裡就可以了! 複雜度便可以降低至O(n)。

### 補充: 迴圈版本
等同於上面遞迴的迴圈版本，可能會比較好理解一點?
```c=
void reverse(char *s) {
    int len = 0;
   
    while( *(s + len)!='\0')
        len++;
   
    int mid = len / 2;
    
    for(int i = 0; i < mid; i++)
        swap(s + i, s + len - i - 1);
 
}
```
## TODO
- [ ] 研究 [MapReduce with POSIX Thread](https://hackmd.io/@top30339/Hkb-lXkyg?type=view)，深入了解何謂 MapReduce
- [ ] 研究 [Functional Programming 風格的 C 語言實作](https://hackmd.io/@sysprog/c-functional-programming)，深入了解何謂 functional programming