Dav*_*nds 307
通常,我通过将通常传递给递归函数的参数推送到堆栈上来通过迭代算法替换递归算法.实际上,您正在用自己的程序替换程序堆栈.
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);
编辑:文章Stacks和Recursion Elimination(或Article Backup链接)详细介绍了这个主题.
bob*_*olt 75
实际上,最常见的方法是保留自己的堆栈.这是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;
}
}
显然,这个例子没有检查堆栈边界......实际上你可以根据给定左右值的最坏情况来调整堆栈的大小.但是你明白了.
T. *_*ter 46
似乎没有人解决递归函数在正文中多次调用自身的问题,并处理递归到递归中的特定点(即不是原始递归).据说每次递归都可以转换为迭代,所以看起来这应该是可能的.
我刚刚想出了一个如何做到这一点的C#示例.假设您具有以下递归函数,其行为类似于后序遍历,并且AbcTreeNode是具有指针a,b,c的3-ary树.
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();
}
}
Chr*_*fer 32
努力使你的递归调用Tail Recursion(递归,其中最后一个语句是递归调用).一旦你有了,将其转换为迭代通常很容易.
cop*_*pro 19
嗯,通常,通过简单地使用存储变量,可以将递归模仿为迭代.请注意,递归和迭代通常是等效的; 一个人几乎总能转换成另一个人.尾递归函数很容易转换为迭代函数.只需将累加器变量设为局部变量,然后迭代而不是递归.这是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;
}
知道我,我可能在代码中犯了一个错误,但这个想法就在那里.
小智 14
即使使用堆栈也不会将递归算法转换为迭代算法.正常递归是基于函数的递归,如果我们使用堆栈,那么它将成为基于堆栈的递归.但它仍然是递归.
对于递归算法,空间复杂度为O(N),时间复杂度为O(N).对于迭代算法,空间复杂度为O(1),时间复杂度为O(N).
但是如果我们使用堆栈的东西在复杂性方面保持不变.我认为只有尾递归可以转换为迭代.
Che*_*han 13
该堆和递归消除文章捕捉外部化上堆栈帧的想法,但不提供直接的和可重复的方式转换.下面是一个.
在转换为迭代代码时,必须意识到递归调用可能来自任意深度的代码块.它不仅仅是参数,还包括返回到仍然要执行的逻辑的点和参与后续条件的变量的状态,这很重要.下面是一个非常简单的方法,可以转换为迭代代码,只需更改.
考虑这个递归代码:
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<stackitem> 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)
{
+++++++++++++++++++++++++
vector<stackitem> v;
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);
}
}
想想真正需要堆栈的东西：
如果我们考虑递归模式为：
if(task can be done directly) {
return result of doing task directly
} else {
split task into two or more parts
solve for each part (possibly by recursing)
return result constructed by combining these solutions
}
比如经典的河内塔
if(the number of discs to move is 1) {
just move it
} else {
move n-1 discs to the spare peg
move the remaining disc to the target peg
move n-1 discs from the spare peg to the target peg, using the current peg as a spare
}
这可以转换为在显式堆栈上工作的循环，将其重述为：
place seed task on stack
while stack is not empty
take a task off the stack
if(task can be done directly) {
Do it
} else {
Split task into two or more parts
Place task to consolidate results on stack
Place each task on stack
}
}
对于河内塔，这变为：
stack.push(new Task(size, from, to, spare));
while(! stack.isEmpty()) {
task = stack.pop();
if(task.size() = 1) {
just move it
} else {
stack.push(new Task(task.size() -1, task.spare(), task,to(), task,from()));
stack.push(new Task(1, task.from(), task.to(), task.spare()));
stack.push(new Task(task.size() -1, task.from(), task.spare(), task.to()));
}
}
关于如何定义堆栈，这里有相当大的灵活性。您可以使堆栈成为Command执行复杂操作的对象列表。或者，您可以反其道而行之，使其成为更简单类型的列表（例如，“任务”可能是 堆栈上的 4 个元素int，而不是 堆栈上的一个元素Task）。
所有这一切意味着堆栈的内存在堆中而不是在 Java 执行堆栈中，但这很有用，因为您可以对其进行更多控制。
通常,避免堆栈溢出的技术是递归函数,称为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<int>.CreateSingular(i => i >= ar.Length, i => 0)
.RecursiveCall((i, rv) => i + 1)
.Do((i, rv) => ar[i] + rv)
.Execute(0);
}
| 归档时间： |
|
| 查看次数： |
119688 次 |
| 最近记录： |