在我多年的编程中,我已经使用递归来解决简单的问题,但我完全清楚,有时你需要迭代,因为内存/速度问题.
所以,在很久以前的某个时候,我去尝试找出是否存在任何"模式"或文本书的方式将常见的递归方法转换为迭代而没有发现任何东西.或者至少我记不住任何事都会有所帮助.
有一般规则吗？
有"模式"吗？
David Segond.. 307
通常,我通过将通常传递给递归函数的参数推送到堆栈上来通过迭代算法替换递归算法.实际上,您正在用自己的程序替换程序堆栈.
Stack
注意:如果您内部有多个递归调用,并且您希望保留调用的顺序,则必须以相反的顺序将它们添加到堆栈中:
foo(first); foo(second);
必须被替换
stack.push(second); stack.push(first);
编辑:文章Stacks和Recursion Elimination(或Article Backup链接)详细介绍了这个主题.
通常,我通过将通常传递给递归函数的参数推送到堆栈上来通过迭代算法替换递归算法.实际上,您正在用自己的程序替换程序堆栈.
Stack
注意:如果您内部有多个递归调用,并且您希望保留调用的顺序,则必须以相反的顺序将它们添加到堆栈中:
foo(first); foo(second);
必须被替换
stack.push(second); stack.push(first);
编辑:文章Stacks和Recursion Elimination(或Article Backup链接)详细介绍了这个主题.
实际上,最常见的方法是保留自己的堆栈.这是C中的递归quicksort函数:
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;
}
}
显然,这个例子没有检查堆栈边界......实际上你可以根据给定左右值的最坏情况来调整堆栈的大小.但是你明白了.
似乎没有人解决递归函数在正文中多次调用自身的问题,并处理递归到递归中的特定点(即不是原始递归).据说每次递归都可以转换为迭代,所以看起来这应该是可能的.
我刚刚想出了一个如何做到这一点的C#示例.假设您具有以下递归函数,其行为类似于后序遍历,并且AbcTreeNode是具有指针a,b,c的3-ary树.
public static void AbcRecursiveTraversal(this AbcTreeNode x, Listlist) { 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();
}
}
努力使你的递归调用Tail Recursion(递归,其中最后一个语句是递归调用).一旦你有了,将其转换为迭代通常很容易.
嗯,通常,通过简单地使用存储变量,可以将递归模仿为迭代.请注意,递归和迭代通常是等效的; 一个人几乎总能转换成另一个人.尾递归函数很容易转换为迭代函数.只需将累加器变量设为局部变量,然后迭代而不是递归.这是C++中的一个例子(C不是因为使用了默认参数):
// tail-recursive
int factorial (int n, int acc = 1)
{
if (n == 1)
return acc;
else
return factorial(n - 1, acc * n);
}
// iterative
int factorial (int n)
{
int acc = 1;
for (; n > 1; --n)
acc *= n;
return acc;
}
知道我,我可能在代码中犯了一个错误,但这个想法就在那里.
即使使用堆栈也不会将递归算法转换为迭代算法.正常递归是基于函数的递归,如果我们使用堆栈,那么它将成为基于堆栈的递归.但它仍然是递归.
对于递归算法,空间复杂度为O(N),时间复杂度为O(N).对于迭代算法,空间复杂度为O(1),时间复杂度为O(N).
但是如果我们使用堆栈的东西在复杂性方面保持不变.我认为只有尾递归可以转换为迭代.
该堆和递归消除文章捕捉外部化上堆栈帧的想法,但不提供直接的和可重复的方式转换.下面是一个.
在转换为迭代代码时,必须意识到递归调用可能来自任意深度的代码块.它不仅仅是参数,还包括返回到仍然要执行的逻辑的点和参与后续条件的变量的状态,这很重要.下面是一个非常简单的方法,可以转换为迭代代码,只需更改.
考虑这个递归代码:
struct tnode
{
tnode(int n) : data(n), left(0), right(0) {}
tnode *left, *right;
int data;
};
void insertnode_recur(tnode *node, int num)
{
if(node->data <= num)
{
if(node->right == NULL)
node->right = new tnode(num);
else
insertnode(node->right, num);
}
else
{
if(node->left == NULL)
node->left = new tnode(num);
else
insertnode(node->left, num);
}
}
迭代代码:
// Identify the stack variables that need to be preserved across stack
// invocations, that is, across iterations and wrap them in an object
struct stackitem
{
stackitem(tnode *t, int n) : node(t), num(n), ra(0) {}
tnode *node; int num;
int ra; //to point of return
};
void insertnode_iter(tnode *node, int num)
{
vector v;
//pushing a stackitem is equivalent to making a recursive call.
v.push_back(stackitem(node, num));
while(v.size())
{
// taking a modifiable reference to the stack item makes prepending
// 'si.' to auto variables in recursive logic suffice
// e.g., instead of num, replace with si.num.
stackitem &si = v.back();
switch(si.ra)
{
// this jump simulates resuming execution after return from recursive
// call
case 1: goto ra1;
case 2: goto ra2;
default: break;
}
if(si.node->data <= si.num)
{
if(si.node->right == NULL)
si.node->right = new tnode(si.num);
else
{
// replace a recursive call with below statements
// (a) save return point,
// (b) push stack item with new stackitem,
// (c) continue statement to make loop pick up and start
// processing new stack item,
// (d) a return point label
// (e) optional semi-colon, if resume point is an end
// of a block.
si.ra=1;
v.push_back(stackitem(si.node->right, si.num));
continue;
ra1: ;
}
}
else
{
if(si.node->left == NULL)
si.node->left = new tnode(si.num);
else
{
si.ra=2;
v.push_back(stackitem(si.node->left, si.num));
continue;
ra2: ;
}
}
v.pop_back();
}
}
注意代码的结构如何仍然适用于递归逻辑,并且修改是最小的,从而导致更少的错误.为了比较,我用++和 - 标记了变化.除了v.push_back之外,大多数新插入的块对于任何转换的迭代逻辑都是通用的
void insertnode_iter(tnode *node, int num)
{
+++++++++++++++++++++++++
vectorv; v.push_back(stackitem(node, num)); while(v.size()) { stackitem &si = v.back(); switch(si.ra) { case 1: goto ra1; case 2: goto ra2; default: break; }
------------------------
if(si.node->data <= si.num)
{
if(si.node->right == NULL)
si.node->right = new tnode(si.num);
else
{
+++++++++++++++++++++++++
si.ra=1;
v.push_back(stackitem(si.node->right, si.num));
continue;
ra1: ;
-------------------------
}
}
else
{
if(si.node->left == NULL)
si.node->left = new tnode(si.num);
else
{
+++++++++++++++++++++++++
si.ra=2;
v.push_back(stackitem(si.node->left, si.num));
continue;
ra2: ;
-------------------------
}
}
+++++++++++++++++++++++++
v.pop_back();
}
-------------------------
}
搜索谷歌"延续传递风格".转换为尾递归样式有一个通用的过程; 还有一个将尾递归函数转换为循环的通用过程.
只是消磨时间......一个递归函数
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
foo(node->left);
foo(node->right);
}
可以转换为
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
stack.push(node->right);
stack.push(node->left);
while(!stack.empty()) {
node1 = stack.pop();
if(node1 == NULL)
continue;
// Do something with node1...
stack.push(node1->right);
stack.push(node1->left);
}
}
通常,避免堆栈溢出的技术是递归函数,称为trampoline技术,Java开发人员广泛采用.
但是,对于C#,这里有一个小帮助方法,可以将递归函数转换为迭代函数,而无需更改逻辑或使代码易于理解.C#是一种非常好的语言,可以用它来实现惊人的东西.
它的工作原理是通过辅助方法包装方法的一部分.例如以下递归函数:
int Sum(int index, int[] array)
{
//This is the termination condition
if (int >= array.Length)
//This is the returning value when termination condition is true
return 0;
//This is the recursive call
var sumofrest = Sum(index+1, array);
//This is the work to do with the current item and the
//result of recursive call
return array[index]+sumofrest;
}
变成:
int Sum(int[] ar)
{
return RecursionHelper.CreateSingular(i => i >= ar.Length, i => 0)
.RecursiveCall((i, rv) => i + 1)
.Do((i, rv) => ar[i] + rv)
.Execute(0);
}
京公网安备 11010802040832号 | 京ICP备19059560号-6 