如何用堆棧數據結構替換遞歸函數調用？

Question

我有一個遞歸調用函數：

void func(int a, bool arr[]) { 
    ... 
    if (...) { 
     func(a, arr); 
    } 
} 

而且從我的主要代碼中調用它像

int int_var = 0; 
bool bool_array[10]; 
func(int_var, bool_array); 

現在我想用一組數據結構來代替該函數的遞歸調用。

我該怎麼做，例如使用std::stack？

Answer 1

用循環替換遞歸調用並使用std::stack<>非常簡單。

函數調用使用程序/線程內部函數調用堆棧，因此對該函數的遞歸調用僅僅意味着推送堆棧上的實際參數值。
函數返回後，結果被確定，並從堆棧中彈出。

爲了讓更適合的例子，我已經取代你的bool[]陣列，具有std::vector<bool>：

struct params { 
    int a; 
    std::vector<bool> arr; 
}; 

std::stack<params> myStack; 

int int_var = 0; 
std::vector<bool> bool_array; 
// put an initial value onto the stack 
myStack.push(params{int_var,bool_array}); 
while(!myStack.empty()) { 
    // compute int_var and the bool_array 
    if(/* ... */) { 
     myStack.push(params{int_var,bool_array}); 
    } 
    else { 
     params p = myStack.top(); 
     myStack.pop(); 
     // handle results of the previous computation 
    } 
}