探索c#之尾遞歸編譯器優(yōu)化

閱讀目錄:

1. 遞歸運(yùn)用
2. 尾遞歸優(yōu)化
3. 編譯器優(yōu)化

遞歸運(yùn)用

一個(gè)函數(shù)直接或間接的調(diào)用自身，這個(gè)函數(shù)即可叫做遞歸函數(shù)。

• 遞歸主要功能是把問(wèn)題轉(zhuǎn)換成較小規(guī)模的子問(wèn)題，以子問(wèn)題的解去逐漸逼近最終結(jié)果。

• 遞歸最重要的是邊界條件，這個(gè)邊界是整個(gè)遞歸的終止條件。

static int RecFact(int x){    if (x == 0)        return 1;    return x * RecFact(x - 1);}RecFact(10);

上面是個(gè)經(jīng)典階乘函數(shù)的實(shí)現(xiàn)。這里分2步：

• 轉(zhuǎn)換，把10的階乘轉(zhuǎn)化成10*9!，10(9*8!)....每次轉(zhuǎn)換規(guī)模就變的更小。
• 逼近，轉(zhuǎn)換到最小規(guī)模時(shí)0!，求解1。開始逆向合并逐漸逼近到10,得出解。

這里的x==0就是我們的邊界條件(即終止條件)，也有的依賴外部變量為邊界。

如果一個(gè)遞歸函數(shù)沒(méi)有邊界，也就無(wú)法停止(無(wú)限循環(huán)至內(nèi)存溢出)，當(dāng)然這樣也沒(méi)什么意義。

RecFact調(diào)用堆棧：

常見使用場(chǎng)景：

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

尾遞歸優(yōu)化

當(dāng)邊界不明確的時(shí)候，遞歸就很容易出現(xiàn)溢出問(wèn)題。

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

為了優(yōu)化堆棧占用問(wèn)題，從而提出尾遞歸優(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)化的核心思想。

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

編譯器優(yōu)化

尾遞歸優(yōu)化，看起來(lái)是蠻美好的，但在net中卻有點(diǎn)亂糟糟的感覺(jué)。

• Net在C#語(yǔ)言中是JIT編譯成匯編時(shí)進(jìn)行優(yōu)化的。
• Net在IL上，有個(gè)特殊指令tail去實(shí)現(xiàn)尾遞歸優(yōu)化的(F#中)。

我們執(zhí)行 TailRecursion(0)(x==1000000) 得出如下結(jié)論：

C#/64位/Release是有JIT編譯器進(jìn)行尾遞歸優(yōu)化的(非C#編譯器優(yōu)化)。

C#/32位或C#/Debug模式中JIT是不進(jìn)行優(yōu)化的。

F#在優(yōu)化尾遞歸也分2種情況：

1、 簡(jiǎn)單的尾遞歸優(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ù)雜的尾遞歸，F(xiàn)#編譯器會(huì)生成IL指令Tail進(jìn)行優(yōu)化，如下：

let TailRecursion2 a cont = cont (a + 1)  

優(yōu)化成：

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

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

總結(jié)

在C#語(yǔ)言(過(guò)程式/面向?qū)ο缶幊趟枷?中，優(yōu)先考慮的是循環(huán)，而不是遞歸/尾遞歸。 但在函數(shù)式編程思想當(dāng)中，遞歸/尾遞歸使用則是主流用法，就像在C#使用循環(huán)一樣。

參考資料

http://volgarev.me/blog/62412678347

http://stackoverflow.com/questions/15864670/generate-tail-call-opcode