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在此情況下是較好的寫法。