Edison.X. Blog

先決條件是：能用 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 之動作。

麻煩些沒錯，但認為這種方式較屬折衷。

持有不同看法之網友請提供討論，謝謝。