遞歸運用

一個函數直接或間接的調用自身，這個函數即可叫做遞歸函數。

遞歸主要功能是把問題轉換成較小規(guī)模的子問題，以子問題的解去逐漸逼近最終結果。
遞歸最重要的是邊界條件，這個邊界是整個遞歸的終止條件。

上面是個經典階乘函數的實現。這里分2步：

1.轉換，把10的階乘轉化成10*9!，10(9*8!)....每次轉換規(guī)模就變的更小。
2.逼近，轉換到最小規(guī)模時0!，求解1。開始逆向合并逐漸逼近到10,得出解。
這里的x==0就是我們的邊界條件(即終止條件)，也有的依賴外部變量為邊界。

如果一個遞歸函數沒有邊界，也就無法停止(無限循環(huán)至內存溢出)，當然這樣也沒什么意義。

RecFact調用堆棧：

常見使用場景：

1.階乘/斐波那契數列/漢諾塔
2.遍歷硬盤文件
3.InnerExceptions異常撲捉(exception.InnerException==null)

尾遞歸優(yōu)化

當邊界不明確的時候，遞歸就很容易出現溢出問題。

在階乘過程中，堆棧需要保存每次(RecFact)調用的返回地址及當時所有的局部變量狀態(tài)，期間堆棧空間是無法釋放的(即容易出現溢出)。

為了優(yōu)化堆棧占用問題，從而提出尾遞歸優(yōu)化的辦法。

使用尾遞歸堆棧可以不用保存上次的函數返回地址/各種狀態(tài)值，而方法遺留在堆棧上的數據完全可以釋放掉，這是尾遞歸優(yōu)化的核心思想。

由于尾遞歸期間，堆棧是可以釋放/再利用的，也就解決遞歸過深而引起的溢出問題，這也是尾遞歸的優(yōu)勢所在。

編譯器優(yōu)化

尾遞歸優(yōu)化，看起來是蠻美好的，但在net中卻有點亂糟糟的感覺。

1.Net在C#語言中是JIT編譯成匯編時進行優(yōu)化的。
2.Net在IL上，有個特殊指令tail去實現尾遞歸優(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)，如下：

優(yōu)化成：

如何定義復雜的尾遞歸呢？通常是后繼傳遞模式(CPS)。

F#中在debug模式下，需要在編譯時配置：

總結

在C#語言(過程式/面向對象編程思想)中，優(yōu)先考慮的是循環(huán)，而不是遞歸/尾遞歸。 但在函數式編程思想當中，遞歸/尾遞歸使用則是主流用法，就像在C#使用循環(huán)一樣。

最新評論