〈演算法與資料結構 #1〉Recursion 遞迴函式

1. 何謂遞迴

遞迴(Recursive)簡單來說就是會呼叫自己的函式

遞迴是透過將本來的問題拆分成數個小問題，並進而解決的方法，而拆分的過程中最終會達到所謂的'Base case'(可以理解為遞迴的終止條件)，也就是該問題的能夠拆解的最小單位後，再逐步回推至最初的函式並回傳結果。

遞迴的應用範圍眾多，比如linked list的處理和binary tree的遍歷，都可以透過遞迴輕鬆完成。在第4點會有相關例子。

2. 遞迴(Recursion) v.s. 迭代(iteration)

迭代(iteration)適用於迴圈(loop)，與用於函式的遞迴不同，兩者往往能達到相同的效果，但可以視情況選擇較佳的一方。

兩者的挑選可以想成"時間複雜度"和"code長度"的一個trade-off，在時間複雜度上，迭代的時間複雜度可以透過迴圈的次數算得，然而遞迴因為會反覆呼叫自身函式，很容易導致時間複雜度遽升。(詳細內容可參考這裡)但遞迴在表達時往往比迭代更為簡潔，因此更具有可讀性和維護性。

3. C++實做

一個經典的例子：費波納契數列，用遞迴的方式怎麼寫。

#include <iostream>
#include <string>
using namespace std;

int fibNumber(int n){
    // n<=1是base case
    if(n<=1){
        return n;
    }
    else{
        return fibNumber(n-1)+fibNumber(n-2);
    }
}

int main(void){
    int i;
    for(i=1;i<=10;i++){
        cout<<fibNumber(i)<<endl; //印出數列前十項
    }
    system("pause");
    return 0;
}

輸出結果：

1
1
2
3
5
8
13
21
34
55
請按任意鍵繼續 . . .

4.Leetcode解題範例

我們來看看經典的Leetcode 21. Merge Two Sorted Lists這是一題linked list的相關題目，可以使用recursion或iteration來解題，並比較兩者間的差異。

先來看看recursive的解法(參考詳解區Knockcat大大的答案)

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
       if (list1 == NULL){
           return list2;
       } else if (list2 == NULL){
           return list1;
       }

       if(list1->val <= list2->val){
           list1->next = mergeTwoLists(list1->next, list2);
           return list1;
       } else {
           list2->next = mergeTwoLists(list1, list2->next);
           return list2;
       }
    }
};

所用時間：4ms

接著是Iteration

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == NULL)
            return list2;
        if(list2 == NULL)
            return list1;

        ListNode * ptr = list1;
        if(list1 -> val > list2 -> val)
        {
            ptr = list2;
            list2 = list2 -> next;
        }
        else
        {
            list1 = list1 -> next;
        }
        ListNode *curr = ptr;

        while(list1 &&  list2)
        {
            if(list1 -> val < list2 -> val){
                curr->next = list1;
                list1 = list1 -> next;
            }
            else{
                curr->next = list2;
                list2 = list2 -> next;
            }
            curr = curr -> next;     
        }
        if(!list1)
            curr -> next = list2;
        else
            curr -> next = list1;
        return ptr;
    }
};

所用時間：6ms

重點複習一下Recursion的解法，我們可以看到Base case是當其中一個list==NULL時開始回傳，而最後則是將改寫過後的list1或list2當成最終回傳值。
比較過後可以發現，recursion的寫法在程式碼上的簡潔程度是高上許多的，而且單就此題而言在時間上也贏過iteration的寫法，因此recursion在此情況下是較好的寫法。