→ MOONRAKER:我也聽不懂 我覺得應該是「如果function overhead很大 12/11 14:56
→ MOONRAKER:(每次執行固定消耗資源) 那麼跑遞迴就很可能會當」？ 12/11 14:57
推 ledia:每次要把一堆 registry 推上 stack 會多耗掉不少時間 12/11 16:04
推 ledia:像這邊每決定一個數字就要 function call 一次 12/11 16:10
→ ledia:時間差就會很明顯 12/11 16:10
( *[1m *[m 為色碼，可以按 Ctrl+V 預覽會顯示的顏色 )
( 未必需要依照此格式，文章條理清楚即可 )
遇到的問題： (題意請描述清楚)
參考上面一篇問題"排序後的兩數列找相同的值"的推文
有人說遞迴跑很大量的話 function overhead會很大
雖然不太清楚這是什麼意思,不過感覺就是不好的東西,要避免
所以推文說stack -> loop
印象中有人說過,迴圈跟遞迴是等價的,遞迴可以寫的迴圈也可以寫
我想嘗試把一個遞迴的程式改成迴圈,但遇到困難
主要的困難點是
我會在呼叫函式前做一些設值的動作,然後當呼叫完函式之後我要把這些動作恢復
不知道我該怎麼做,是不是我要寫一個stack去記錄我所做的動作?
如果我寫了一個stack,那我要如何知道這個stack要多大?
以及,如果一樣用到stack,那當我迴圈跑很深的時候是不是也會有overhead的問題?
我這個函式很簡單,只是想要產生一組數列
每組數列的數字不重複 1 2 3 4 5 ... LIST_SIZE每個數字都只能出現一次
而且每次產生的順序不同
希望得到的正確結果：
假設數列大小是LIST_SIZE 假設是3
則結果如下
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
程式跑出來的錯誤結果：
沒錯
開發平台： (例: VC++ or gcc/g++ or Dev-C++, Windows or Linux)
VC6
有問題的code： (請善用置底文標色功能)
#define LIST_SIZE EDGE_SIZE
#define NEVER_USE -1
void SetLabel(int *NumberList,int ListIndex,int *CheckNumber)
{
int i;
//檢查可行性
if(ListIndex == LIST_SIZE)
{
for(i=0; i<LIST_SIZE; i++)
printf("%2d ",NumberList[i]);
printf("\n");
}
else
for(i=0; i<LIST_SIZE; i++)
{
if(CheckNumber[i] == NEVER_USE)
{
NumberList[ListIndex] = i+1;
CheckNumber[i] = ListIndex;
SetLabel(NumberList,ListIndex+1,CheckNumber);
CheckNumber[i] = NEVER_USE;
}
}
}
補充說明：
我想知道改成LOOP的話怎麼處理這部分
CheckNumber[i] = ListIndex;
SetLabel(NumberList,ListIndex+1,CheckNumber);
CheckNumber[i] = NEVER_USE;
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.169.53.223