先決條件是:能用 loop 就用 loop 取代掉 recursive 。
對於這篇文章若有任何意見,請不吝提出。
一般在搞演算法類的東西時,不少機會會用到 recursive 之類的東西,
下述以 recursive 達成 power set (一集合元素裡之所有子集合)目的之程式碼為探討,
一份 demo code 可能長這樣
#include <stdio.h> #define MAX 200 int data[MAX]; // 實際資料 char is_used[MAX]; // 控制flag int size; // 實際size int total; // 計算共幾組解答 void print() { int i; printf("\n > {"); for(i=0; i<size; ++i) if(is_used[i]) printf("%2d", data[i]); printf(" } "); } void power_set(int pos) { int i; if(pos==size) { // 跑完 size 個 print(); // 輸出解答 total++; // 總數 + 1 } else { is_used[pos]=0; // 不選 power_set(pos+1); // 往下個跑 is_used[pos]=1; // 選 power_set(pos+1); // 往下個跑 } } int main() { int i; // assign size and data size = 3; for(i=0; i<size; ++i) { is_used[i] = 0; data[i] = i+1; } // run power_set power_set(0); printf("\n > Total : %d\n", total); return 0; }
註明,這是一份 demo code (效率非常差的 demo code),
要探討的是在 recursive function 裡面引數是不是只能這麼放?
簡單的說,由於 recursive 實作時,會把需要的引數丟進 stack,
但 stack 大小實為有限,同時在 push、pop 也需要時間,
很明顯的,引數愈少,「正常而言」可以執行較多層,速度也會快「一點點」,
但這種方式是把所需的引數全都用 global 方式去宣告,
個人認為便失去了擴充性問題,再看下面這段 code
#include <stdio.h> #define MAX 200 void print(int *data, char *is_used, unsigned size) { int i; printf("\n > {"); for(i=0; i<size; ++i) if(is_used[i]) printf("%2d", data[i]); printf(" } "); } void next_subset(int *data, char *is_used, int n, int cur_size, int *total) { if(cur_size==n) { ++(*total); print(data, is_used, n); } else { is_used[cur_size] = 0; // don't sel next_subset(data,is_used, n, cur_size+1, total); is_used[cur_size] = 1; // sel next_subset(data, is_used, n, cur_size+1, total); } } int main() { int data[] = {1, 2, 3}; int n = sizeof(data) / sizeof(*data); int total = 0; char is_used[MAX] = {0};; next_subset(data, is_used, n, 0, &total); printf("\n > Total : %d\n", total); return 0; }
這段 code 恰恰相反,它把所有的全域變數,全都塞到 function 裡面當引數,
但相對的在 recursive 做呼叫時, push、pop stack 動作,成本相對提昇,
至於擴充性會不會比較好?視個人、問題而定。
但若為筆者所設計,將會為上述之
size、is_used、pos
做成 static member,放在另一份 .c / .cpp 裡面,
也就是這樣步驟還有多一個 initialize 之動作。
麻煩些沒錯,但認為這種方式較屬折衷。
持有不同看法之網友請提供討論,謝謝。
全站熱搜