從遞歸到迭代的方法在我多年的編程中，我經常使用遞歸來解決簡單的問題，但我完全意識到，有時由于內存/速度問題，您需要迭代。所以，在很久以前的某個時候，我試著去尋找是否存在任何“模式”或教科書方法來將一種常見的遞歸方法轉換為迭代，卻一無所獲?；蛘咧辽傥矣洃浿械娜魏螙|西都不會有幫助。有一般規則嗎？有“模式”嗎？
3 回答
慕娘9325324
TA貢獻1783條經驗 獲得超4個贊
通常，我將通常傳遞給遞歸函數的參數推送到堆棧中，從而將遞歸算法替換為迭代算法。實際上，您正在將程序堆棧替換為您自己的程序堆棧。
Stack<Object>?stack;
stack.push(first_object);
while(?!stack.isEmpty()?)?{
???//?Do?something
???my_object?=?stack.pop();
??//?Push?other?objects?on?the?stack.
}注意：如果您的內部有多個遞歸調用，并且希望保留調用的順序，則必須將它們以相反的順序添加到堆棧中：
foo(first); foo(second);
必須代之以
stack.push(second); stack.push(first);
ABOUTYOU
TA貢獻1812條經驗 獲得超5個贊
void quicksort(int* array, int left, int right)
{
if(left >= right)
return;
int index = partition(array, left, right);
quicksort(array, left, index - 1);
quicksort(array, index + 1, right);
}void quicksort(int *array, int left, int right)
{
int stack[1024];
int i=0;
stack[i++] = left;
stack[i++] = right;
while (i > 0)
{
right = stack[--i];
left = stack[--i];
if (left >= right)
continue;
int index = partition(array, left, right);
stack[i++] = left;
stack[i++] = index - 1;
stack[i++] = index + 1;
stack[i++] = right;
}
}
尚方寶劍之說
TA貢獻1788條經驗 獲得超4個贊
似乎沒有人討論遞歸函數在主體中多次調用自己的位置，并處理返回到遞歸中的特定點(即不是原始遞歸)的問題。據說每個遞歸都可以轉化為迭代。看來這是可能的。
我只是想出了一個C#的例子來說明如何做到這一點。假設您有下面的遞歸函數，它的作用類似于一個后繼遍歷，而AbcTreeNode是一個具有指針a、b、c的三叉樹。
public?static?void?AbcRecursiveTraversal(this?AbcTreeNode?x,?List<int>?list)?{
????????if?(x?!=?null)?{
????????????AbcRecursiveTraversal(x.a,?list);
????????????AbcRecursiveTraversal(x.b,?list);
????????????AbcRecursiveTraversal(x.c,?list);
????????????list.Add(x.key);//finally?visit?root
????????}
}迭代解決方案：
????????int??address?=?null;
????????AbcTreeNode?x?=?null;
????????x?=?root;
????????address?=?A;
????????stack.Push(x);
????????stack.Push(null)????
????????while?(stack.Count?>?0)?{
????????????bool?@return?=?x?==?null;
????????????if?(@return?==?false)?{
????????????????switch?(address)?{
????????????????????case?A://???
????????????????????????stack.Push(x);
????????????????????????stack.Push(B);
????????????????????????x?=?x.a;
????????????????????????address?=?A;
????????????????????????break;
????????????????????case?B:
????????????????????????stack.Push(x);
????????????????????????stack.Push(C);
????????????????????????x?=?x.b;
????????????????????????address?=?A;
????????????????????????break;
????????????????????case?C:
????????????????????????stack.Push(x);
????????????????????????stack.Push(null);
????????????????????????x?=?x.c;
????????????????????????address?=?A;
????????????????????????break;
????????????????????case?null:
????????????????????????list_iterative.Add(x.key);
????????????????????????@return?=?true;
????????????????????????break;
????????????????}
????????????}
????????????if?(@return?==?true)?{
????????????????address?=?(int?)stack.Pop();
????????????????x?=?(AbcTreeNode)stack.Pop();
????????????}
????????}添加回答
舉報
0/150
提交
取消