由于C＃不支持递归调用的优化非常好（例如尾递归）。看来我必须将我的代码风格从函数式编程切换到我不熟悉的东西。如何使用堆栈重写递归方法？
我知道有时候迭代方法替代存在一个递归方法，但通常它是很难找到一个有效率的。
现在，在一般情况下，我相信所有的递归方法可以用stack<T>数据结构以某种方式被改写。
我在哪里可以找到的教程或引进或一般规则呢？
例如，如果我想重写最大公约数的方法？给定的M> N
int gcd(int m, int n)
{
if (n==0)
return m;
else
return gcd(n,m%n);
}
更新
也许这是一个坏例子，因为它确实是尾递归。 Plz只是忽略了这个事实，并认为这是一个正常的递归方法。
由于您的示例方法是尾递归，因此将其翻译为迭代样式很容易，甚至不需要显式堆栈。
这里有一些步骤，可应用于任何递归函数：
步骤1：重写方法，因此调用自身一次（你的方法已经这样做了），都只有一个return语句，使用if和goto代替else，while，for和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的方法开始：
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;
}
如果该方法不是尾递归的方法将需要保存其状态在goto之前，稍后再恢复它。
步骤3：再次拆下goto S：
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：使方法看起来更好：
int gcd(int m, int n)
{
while (n != 0)
{
int old_m = m;
m = n;
n = old_m % n;
}
return m;
}
下面是不是尾的示例 - 递归：
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;
}
在这种情况下，你甚至都不需要一个栈：
int gcd(int m, int n) {
while(n != 0) {
int aux = m;
m = n;
n = aux % n;
}
return m;
}
一般情况下，每一个尾递归算法，你并不需要一个栈，这是后一些编译器可以优化它;但是无需使用调用堆栈即可实现优化！尾递归可以通过一个简单的循环得到实现
如果我们看最简单的情况，从这里推广应该不会太难。
假设我们有一个看起来像这样的方法：
public void CountToTenInReverse(int curNum)
{
if (curNum >= 11)
return;
CountToTen(curNum + 1);
Console.WriteLine(curNum);
}
让我们看看调用堆栈CountToTenInReverse(1)看看有什么实际发生的情况。经过十分的来电，我们有这样的：
[ CountToTenInReverse(10) ] <---- Top of stack
[ CountToTenInReverse(9) ]
[ CountToTenInReverse(8) ]
[ CountToTenInReverse(7) ]
[ CountToTenInReverse(6) ]
[ CountToTenInReverse(5) ]
[ CountToTenInReverse(4) ]
[ CountToTenInReverse(3) ]
[ CountToTenInReverse(2) ]
[ CountToTenInReverse(1) ] <---- Bottom of stack
第十个呼叫后，当我们走，我们会打的基本情况，并开始展开堆栈，印数。在的话，那么，我们的算法是“数字推到堆栈，停止，当我们打到10个号码，然后弹出并打印出每个数字。”所以让我们用我们自己的堆栈编写：
public void PrintToTenInReverseNoRecursion()
{
Stack<int> myStack = new Stack<int>();
for (int i = 0; i < 10; i++)
{
myStack.Push(i);
}
for (int i = 0; i < 10; i++)
Console.WriteLine(myStack.Pop());
}
现在我们已经成功地将其转换。 （当然，这是可以反复做没有堆栈，但它只是一个例子。）
同样的方法可以采取其他更复杂的算法：看看调用堆栈，然后模仿一下它的用你自己的堆栈做。
我知道这并没有真正回答你如何与堆栈递归调用程序的问题，但确实.NET尾调用的支持优化。由于JIT编译器的存在以及不同CLR语言编译器之间的IL转换，它不像编译语言那么简单或直接。
这就是说，为什么要担心呢？如果是性能问题，则重写该方法并完全消除递归调用。另外，请注意，.NET 4.0在这方面做了大量改进。 Here is some more information on Tail Call Improvements in .NET Framework 4。你可能担心一个非问题。
您的gcd示例中没有收藏，您为什么需要一个堆栈？你想在那里存储什么？ –
这完全是一个例子..当然，我知道我甚至不需要在这种情况下使用'堆栈'..但它是最简单的情况下，我可以想到关于递归。 – colinfang