由於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