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

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

 

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

 

 

 

edisonx 發表在 痞客邦 PIXNET 留言(0) 人氣()