如何通过使用堆栈重写递归方法? [英] how to rewrite a recursive method by using a stack?
问题描述
由于C#不能很好地支持递归调用的优化(例如尾递归).似乎我必须将代码样式从函数式编程转换为我不熟悉的代码.
Since C# doesn't support the optimization of recursive call very well (e.g tail recursion). It seems I have to switch my code style from functional programming to something I am not familiar with.
我知道有时可以使用迭代方法来代替递归方法，但是通常很难找到一种有效的方法.
I know sometimes iterative method alternative exists to a recursion method, but usually it is quite hard to find an efficient one.
现在，一般而言，我相信可以通过某种方式使用 stack< T> 数据结构来重写所有递归方法.
Now, in generally, I believe all recursive methods can be rewritten by using stack<T> data structure somehow.
在哪里可以找到本教程或简介或一般规则?
Where can I find the tutorial or introduction or general rule to this?
例如，如果我想重写最大的除数方法怎么办?给定m> n
e.g., what if I wanna rewrite greatest common divisor method? given m>n
int gcd(int m, int n)
{
if (n==0)
return m;
else
return gcd(n,m%n);
}
更新
这可能是一个不好的例子，因为它确实是尾递归的.Plz只是忽略了这一事实，并认为这是一种正常的递归方法.
Probably it is a bad example as it indeed is tail recursive. Plz just ignore the fact and consider it is a normal recursive method.
推荐答案
由于示例方法是尾递归的，因此将其转换为迭代样式很容易，甚至不需要显式堆栈.
Since your example method is tail-recursive, translating it to iterative style is easy and does not even require an explicit stack.
以下是一些可应用于任何递归函数的步骤:
Here are some steps that can be applied to any recursive function:
第1步:重写该方法，使其完全调用一次(您的方法已经执行了此操作)，只有一个 return 语句，并使用 if 和 goto ，而不是 else ， while ， for 和 foreach :
Step 1: Rewrite the method so it calls itself exactly once (your method already does this), has exactly one return statement, and uses if and goto instead of else, while, for and foreach:
int gcd(int m, int n)
{
int result;
if (n == 0)
{
result = m;
goto done;
}
result = gcd(n, m % n);
done:
return result;
}
第2步:将新参数分配给参数，将 goto 分配给方法的开头，以替换递归调用:
Step 2: Replace the recursive call with the assignment of the new arguments to the parameters and a goto to the start of the method:
int gcd(int m, int n)
{
int result;
start:
if (n == 0)
{
result = m;
goto done;
}
int old_m = m;
m = n;
n = old_m % n;
goto start;
done:
return result;
}
如果该方法不是尾部递归的，则该方法将需要先保存其状态，然后再进行恢复.
If the method was not tail-recursive, the method would need to save its state before the goto and restore it later again.
第3步:再次删除 goto :
int gcd(int m, int n)
{
int result;
while (true)
{
if (n == 0)
{
result = m;
break;
}
int old_m = m;
m = n;
n = old_m % n;
}
return result;
}
第4步:使方法看起来更好:
Step 4: Make the method look nicer:
int gcd(int m, int n)
{
while (n != 0)
{
int old_m = m;
m = n;
n = old_m % n;
}
return m;
}
以下是不尾递归的示例:
Here's an example that is not tail-recursive:
int fac(int x)
{
if (x == 0)
{
return 1;
}
return x * fac(x - 1);
}
第1步:
int fac(int x)
{
int result;
if (x == 0)
{
result = 1;
goto end;
}
result = x * fac(x - 1);
end:
return result;
}
第2步:
int fac(int x)
{
Stack<int> stack = new Stack<int>();
int result;
start:
if (x == 0)
{
result = 1;
goto end;
}
stack.Push(x);
x = x - 1;
goto start;
end:
if (stack.Count != 0)
{
x = stack.Pop();
result = x * result;
goto end;
}
return result;
}
第3步:
int fac(int x)
{
Stack<int> stack = new Stack<int>();
int result;
while (true)
{
if (x == 0)
{
result = 1;
break;
}
stack.Push(x);
x = x - 1;
}
while (stack.Count != 0)
{
x = stack.Pop();
result = x * result;
}
return result;
}
第4步:
int fac(int x)
{
Stack<int> stack = new Stack<int>();
while (x != 0)
{
stack.Push(x);
x = x - 1;
}
int result = 1;
while (stack.Count != 0)
{
x = stack.Pop();
result = x * result;
}
return result;
}
这篇关于如何通过使用堆栈重写递归方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
