探索c#之尾遞歸編譯器優化
遞歸運用
一個函數直接或間接的調用自身，這個函數即可叫做遞歸函數。
遞歸主要功能是把問題轉換成較小規模的子問題，以子問題的解去逐漸逼近最終結果。
遞歸最重要的是邊界條件，這個邊界是整個遞歸的終止條件。
static int RecFact(int x)
{
if (x == 0)
return 1;
return x * RecFact(x - 1);
}
RecFact(10);
上面是個經典階乘函數的實現。這裡分2步：
轉換，把10的階乘轉化成10*9!，10(9*8!)....每次轉換規模就變的更小。
逼近，轉換到最小規模時0!，求解1。開始逆向合並逐漸逼近到10,得出解。
這裡的x==0就是我們的邊界條件(即終止條件)，也有的依賴外部變量為邊界。
如果一個遞歸函數沒有邊界，也就無法停止(無限循環至內存溢出)，當然這樣也沒什麼意義。
RecFact調用堆棧：
常見使用場景：
階乘/斐波那契數列/漢諾塔
遍歷硬盤文件
InnerExceptions異常撲捉(exception.InnerException==null)
尾遞歸優化
當邊界不明確的時候，遞歸就很容易出現溢出問題。
在階乘過程中，堆棧需要保存每次(RecFact)調用的返回地址及當時所有的局部變量狀態，期間堆棧空間是無法釋放的(即容易出現溢出)。
為了優化堆棧占用問題，從而提出尾遞歸優化的辦法。
static void Recurse(int x)
{
Console.WriteLine(x);
if (x == 10)
return;
Recurse(x + 1);
}
Recurse(0);
上面這個遞歸和階乘那個區別在於沒有返回值，也就是說堆棧可以不用保存上一次的返回地址/狀態值，這就是尾遞歸優化的思想。
尾遞歸可以解決遞歸過深而引起的溢出問題，因為遞歸期間堆棧是可以釋放/再利用的。
編譯器優化
尾遞歸優化，看起來是蠻美好的，但在net中卻有點亂糟糟的感覺。
Net在C#語言中是JIT編譯成匯編時進行優化的。
Net在IL上，有個特殊指令tail去實現尾遞歸優化的(F#中)。
我們執行 Recurse(0)(x==1000000) 得出如下結論：
C#/64位/Release是有JIT編譯器進行尾遞歸優化的(非C#編譯器優化)。
C#/32位或C#/Debug模式中JIT是不進行優化的。
F#在優化尾遞歸也分2種情況：
1、 簡單的尾遞歸優化成while循環，如下：
let rec Recurse(x) =
if (x = 1000) then true
else Recurse(x + 1)
(方便演示C#呈現)優化成：
public static bool Recurse(int x)
{
while (x != 0x3e8)
{
x++;
}
return true;
}
2、 復雜的尾遞歸，F#編譯器會生成IL指令Tail進行優化，如下：
let Recurse2 a cont = cont (a + 1)
優化成：
如何定義復雜的尾遞歸呢？通常是後繼傳遞模式(CPS)。
F#中在debug模式下，需要在編譯時配置：
總結
在C#語言(過程式/面向對象編程思想)中，優先考慮的是循環，而不是遞歸/尾遞歸。 但在函數式編程思想當中，遞歸/尾遞歸使用則是主流用法，就像在C#使用循環一樣。
