在我多年的编程生涯中,我经常使用递归来解决简单的问题,但我完全意识到,有时由于内存/速度问题,您需要迭代。
所以,在很久以前的某个时候,我去尝试寻找是否存在任何“模式”或教科书上的方法来将常见的递归方法转换为迭代,但一无所获。至少我想不起有什么帮助。
有一般的规则吗? 有“模式”吗?
在我多年的编程生涯中,我经常使用递归来解决简单的问题,但我完全意识到,有时由于内存/速度问题,您需要迭代。
所以,在很久以前的某个时候,我去尝试寻找是否存在任何“模式”或教科书上的方法来将常见的递归方法转换为迭代,但一无所获。至少我想不起有什么帮助。
有一般的规则吗? 有“模式”吗?
当前回答
似乎没有人指出递归函数在主体中调用自己超过一次的位置,并处理返回递归中的特定点(即不是原始递归)。据说每一个递归都可以转化为迭代,所以这似乎是可能的。
我刚刚想出了一个如何做到这一点的c#示例。假设您有以下递归函数,它的作用类似于poststorder遍历,AbcTreeNode是一个带有指针a、b、c的3元树。
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();
}
}
其他回答
另一个使用堆栈将递归函数转换为迭代函数的简单而完整的示例。
#include <iostream>
#include <stack>
using namespace std;
int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }
struct Par
{
int a, b;
Par() : Par(0, 0) {}
Par(int _a, int _b) : a(_a), b(_b) {}
};
int GCDIter(int a, int b)
{
stack<Par> rcstack;
if (b == 0)
return a;
rcstack.push(Par(b, a % b));
Par p;
while (!rcstack.empty())
{
p = rcstack.top();
rcstack.pop();
if (p.b == 0)
continue;
rcstack.push(Par(p.b, p.a % p.b));
}
return p.a;
}
int main()
{
//cout << GCD(24, 36) << endl;
cout << GCDIter(81, 36) << endl;
cin.get();
return 0;
}
实际上,最常见的方法是保留自己的堆栈。下面是一个C语言的递归快速排序函数:
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;
}
}
显然,这个例子没有检查堆栈边界……实际上,你可以根据最坏的情况来确定堆栈的大小。但你懂的。
通常,通过将通常传递给递归函数的参数推入堆栈,我将递归算法替换为迭代算法。事实上,您正在用自己的程序堆栈替换程序堆栈。
var stack = [];
stack.push(firstObject);
// while not empty
while (stack.length) {
// Pop off end of stack.
obj = stack.pop();
// Do stuff.
// Push other objects on the stack as needed.
...
}
注意:如果你在里面有多个递归调用,并且你想要保留调用的顺序,你必须以相反的顺序将它们添加到堆栈:
foo(first);
foo(second);
必须由
stack.push(second);
stack.push(first);
编辑:文章堆栈和递归消除(或文章备份链接)详细介绍了这个主题。
努力使你的递归调用尾部递归(递归的最后一个语句是递归调用)。一旦你有了它,将它转换为迭代通常是相当容易的。
我的例子是用Clojure编写的,但是应该很容易翻译成任何语言。
给定这个函数,当n值较大时StackOverflows:
(defn factorial [n]
(if (< n 2)
1
(*' n (factorial (dec n)))))
我们可以用以下方式定义一个使用自己堆栈的版本:
(defn factorial [n]
(loop [n n
stack []]
(if (< n 2)
(return 1 stack)
;; else loop with new values
(recur (dec n)
;; push function onto stack
(cons (fn [n-1!]
(*' n n-1!))
stack)))))
其中return定义为:
(defn return
[v stack]
(reduce (fn [acc f]
(f acc))
v
stack))
这也适用于更复杂的函数,例如阿克曼函数:
(defn ackermann [m n]
(cond
(zero? m)
(inc n)
(zero? n)
(recur (dec m) 1)
:else
(recur (dec m)
(ackermann m (dec n)))))
可以转化为:
(defn ackermann [m n]
(loop [m m
n n
stack []]
(cond
(zero? m)
(return (inc n) stack)
(zero? n)
(recur (dec m) 1 stack)
:else
(recur m
(dec n)
(cons #(ackermann (dec m) %)
stack)))))