C#中尾遞歸的使用、優(yōu)化及編譯器優(yōu)化
遞歸運用
一個函數(shù)直接或間接的調用自身，這個函數(shù)即可叫做遞歸函數(shù)。
遞歸主要功能是把問題轉換成較小規(guī)模的子問題，以子問題的解去逐漸逼近最終結果。
遞歸最重要的是邊界條件，這個邊界是整個遞歸的終止條件。
static int RecFact(int x)
{
if (x == 0)
return 1;
return x * RecFact(x - 1);
}
RecFact(10);
上面是個經典階乘函數(shù)的實現(xiàn)。這里分2步：
1.轉換，把10的階乘轉化成10*9!，10(9*8!)....每次轉換規(guī)模就變的更小。
2.逼近，轉換到最小規(guī)模時0!，求解1。開始逆向合并逐漸逼近到10,得出解。
這里的x==0就是我們的邊界條件(即終止條件)，也有的依賴外部變量為邊界。
如果一個遞歸函數(shù)沒有邊界，也就無法停止(無限循環(huán)至內存溢出)，當然這樣也沒什么意義。
RecFact調用堆棧：
常見使用場景：
1.階乘/斐波那契數(shù)列/漢諾塔
2.遍歷硬盤文件
3.InnerExceptions異常撲捉(exception.InnerException==null)
尾遞歸優(yōu)化
當邊界不明確的時候，遞歸就很容易出現(xiàn)溢出問題。
在階乘過程中，堆棧需要保存每次(RecFact)調用的返回地址及當時所有的局部變量狀態(tài)，期間堆棧空間是無法釋放的(即容易出現(xiàn)溢出)。
為了優(yōu)化堆棧占用問題，從而提出尾遞歸優(yōu)化的辦法。
static void TailRecursion(int x)
{
Console.WriteLine(x);
if (x == 10)
return;
TailRecursion(x + 1);
}
TailRecursion(0);
使用尾遞歸堆棧可以不用保存上次的函數(shù)返回地址/各種狀態(tài)值，而方法遺留在堆棧上的數(shù)據(jù)完全可以釋放掉，這是尾遞歸優(yōu)化的核心思想。
由于尾遞歸期間，堆棧是可以釋放/再利用的，也就解決遞歸過深而引起的溢出問題，這也是尾遞歸的優(yōu)勢所在。
編譯器優(yōu)化
尾遞歸優(yōu)化，看起來是蠻美好的，但在net中卻有點亂糟糟的感覺。
1.Net在C#語言中是JIT編譯成匯編時進行優(yōu)化的。
2.Net在IL上，有個特殊指令tail去實現(xiàn)尾遞歸優(yōu)化的(F#中)。
我們執(zhí)行 TailRecursion(0)(x==1000000) 得出如下結論：
C#/64位/Release是有JIT編譯器進行尾遞歸優(yōu)化的(非C#編譯器優(yōu)化)。
C#/32位或C#/Debug模式中JIT是不進行優(yōu)化的。
F#在優(yōu)化尾遞歸也分2種情況：
1、 簡單的尾遞歸優(yōu)化成while循環(huán)，如下：
let rec TailRecursion(x) =
if (x = 1000) then true
else TailRecursion(x + 1)
(方便演示C#呈現(xiàn))編譯器優(yōu)化成：
public static bool TailRecursion(int x)
{
while (x != 0x3e8)
{
x++;
}
return true;
}
2、 復雜的尾遞歸，F(xiàn)#編譯器會生成IL指令Tail進行優(yōu)化，如下：
let TailRecursion2 a cont = cont (a + 1)
優(yōu)化成：
如何定義復雜的尾遞歸呢？通常是后繼傳遞模式(CPS)。
F#中在debug模式下，需要在編譯時配置：
總結
在C#語言(過程式/面向對象編程思想)中，優(yōu)先考慮的是循環(huán)，而不是遞歸/尾遞歸。 但在函數(shù)式編程思想當中，遞歸/尾遞歸使用則是主流用法，就像在C#使用循環(huán)一樣。
相關文章
Unity?UGUI的PhysicsRaycaster物理射線檢測組件介紹使用
這篇文章主要介紹了Unity?UGUI的PhysicsRaycaster物理射線檢測組件的介紹及使用,有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-07-07
這篇文章主要為大家詳細介紹了C# winfrom實現(xiàn)讀取修改xml的相關資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-05-05
COM是一種二進制接口標準,允許軟件組件在同一進程中、跨進程甚至跨網絡透明地交互,COM接口定義了一組方法和屬性,這些方法和屬性可以通過任何支持該模型的語言調用來訪問,本文給大家介紹了如何在C#中使用COM接口,需要的朋友可以參考下2025-03-03
Yield可以讓你的代碼更加高效并擁有更高的可讀性，我想已經沒有什么借口可以阻止我們學習和使用yield2013-12-12
這篇文章給大家介紹了如何解決winform界面刷新閃爍問題的多種方案,文中通過代碼示例給大家介紹的非常詳細,對大家的學習或工作有一定的幫助,需要的朋友可以參考下2024-02-02
這篇文章介紹了C#日期轉換函數(shù)，有需要的朋友可以參考一下2013-10-10
這篇文章主要為大家詳細介紹了UnityShader3實現(xiàn)2D描邊效果，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-02-02
這篇文章主要介紹了C#基于Modbus三種CRC16校驗方法的性能對比，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-11-11
這篇文章介紹了C#使用MSTest進行單元測試的方法，文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-06-06
這篇文章主要介紹了詳解從零開始---用C#制作掃雷游戲，非常具有實用價值，需要的朋友可以參考下2017-06-06