for循環遞歸迭代

我推廣我有一個類似的遞歸調用的另一個問題。在我的情況下，使用的變量是字符串，所以我不能簡單地通過值來避免循環中遞歸調用之前和之後的代碼。有沒有辦法將它變成一個迭代循環？請假定循環中的遞歸調用之前和之後的代碼無法更改以使此特定實例有效。for循環遞歸迭代

此代碼測試以查看來自num的任何int整數組合總和是否爲零。 index的原始值爲0，max是我想要在任何給定解決方案中累加的最大數字數。

爲了進一步說明，數字可以重複，所以我不能嘗試所有可能的組合，因爲有無限多的組合。

void findSolution(const vector<int>& nums, vector<int>& my_list, int& mySum, 
int index, const int max) 
{ 
    if(mySum == 0) { 
     /* print my_list and exit(0) */ 
    } 
    if(index < max) { 
     for(int i = 0; i < nums.size(); ++i) { 
      my_list.push_back(nums[i]); 
      mySum += nums[i]; 
      findSolution(nums, my_list, mySum, index+1, max); 
      mySum -= nums[i]; 
      my_list.pop_back(); 
     } 
    } 
}

來源

2012-12-16 user1789919

因此......您希望我們用其他東西替換*那一行*，以使整個事物不會遞歸併獲得正確答案？ – Beta

爲什麼你想擺脫遞歸？如果你認爲它會神奇地加快你的程序，你應該專注於修復算法。正如所寫，你的代碼檢查太多組合的方式，因爲它不知道不同順序中相同數字的總和仍然是相同的總和。（我不清楚你是否打算讓答案重複num的值，但如果你不這樣做，你也會檢查所有這些可能性，這是浪費的，並可能導致錯誤的答案。） – rici

保持手動堆棧。

在你的情況下，遞歸調用的唯一獨立狀態是I的值和索引的值。索引只是遞歸調用深度。

創建一個名爲您的堆棧的int std向量，將其保留爲最大值。在堆棧爲true的情況下替換循環。

在進入循環之前，在棧上按零。

將循環中的鱈魚分成3部分。 A和C是在遞歸調用之前，B是遞歸調用的，C是在之後。包含在C中的是循環頂部的增量，這是在原始代碼中的C之後發生的。

你在循環中做的第一件事是檢查堆棧的頂部是nums大小還是更大。如果是這樣，彈出堆棧，然後執行C並繼續，除非堆棧爲空，在這種情況下中斷。

然後執行A.然後在堆棧上按0並繼續堆棧大小小於最大值。然後執行C.您可以使用標誌變量刪除C代碼重複。

請記住，堆棧頂部會替換對I的任何引用。基本上，我們正在替換一個遞歸調用，它會自動爲我們創建一個堆棧，並手動維護同一個堆棧，但只存儲我們可以拋棄的絕對最小量。循環的開始既是遞歸調用的結束又是循環的開始，所以我們可以避免使用goto。

試試看，看完後再擔心解釋。代碼到位後，有關標誌變量的內容會更有意義。

來源

2012-12-16 12:25:42 Yakk

for循環遞歸迭代

回答

相關問題