關(guān)于遞歸相信大家已經(jīng)熟悉的不能再熟悉了，所以筆者在這里就不多費口舌，不懂的讀者們可以在博客園中找到很多與之相關(guān)的博客。下面我們直接切入正題，開始介紹尾遞歸。

尾遞歸

普通遞歸和尾遞歸如果僅僅只是從代碼的角度出發(fā)來看，我們可能發(fā)現(xiàn)不了他的特點，所以筆者利用兩張堆棧上的圖來展示具體的差距在哪，首先我們來看看普通的遞歸調(diào)用的情況，如下圖1.1所示：

假設(shè)這里執(zhí)行的函數(shù)是Func1，并且Func1中通過遞歸調(diào)用了自己，那么我們可以看到棧上在每次調(diào)用Func1的時候都會重新將函數(shù)返回地址等其他參數(shù)放入棧中，在遞歸次數(shù)較少的情況下，這樣是不會有問題的。但如果遞歸調(diào)用次數(shù)達(dá)到一定的數(shù)量級，則會將?？臻g消耗光。因此，就提出了尾遞歸。而尾遞歸的棧圖如1.2所示：

一樣還是遞歸，但是每次執(zhí)行自身的時候并不會在?？臻g中申請新的空間，類似于for循環(huán)的效果，面對遞歸次數(shù)很多的情況下也不會出現(xiàn)什么問題。但是新的問題就出來了，在C#中編譯器不會做到這一步優(yōu)化，而是在jit編譯器執(zhí)行時才會進(jìn)行優(yōu)化。并且只有64位才進(jìn)行優(yōu)化。在語言的層面上我們也要遵守一定的原則，才能讓編譯器知道去優(yōu)化。當(dāng)然有些喜歡看博客的人可能早就知道尾遞歸就是在最后return的時候調(diào)用自身。我們可以通過一串示意代碼來看尾調(diào)用：

當(dāng)然上面這串代碼會形成一個死循環(huán)，因為這里我們沒有基線條件。下面我們舉一個例子：

這個函數(shù)想必應(yīng)該會比較熟悉，就是計算階乘的。但是我們可以發(fā)現(xiàn)函數(shù)sunfc最后的返回語句并不是直接調(diào)用函數(shù)本身，而是x*sfunc(x -1)，恰恰就是因為前面這個x*就會導(dǎo)致編譯器無法優(yōu)化，從而只能采用普通的遞歸調(diào)用的方式去執(zhí)行，那么我們就需要利用一些模式去改變，首先我們先介紹的是“累加器傳遞模式”，可能名字比較懸乎，其實就是將當(dāng)前的計算結(jié)果傳遞給下一次調(diào)用函數(shù)中，這樣當(dāng)?shù)竭_(dá)基線條件后直接根據(jù)上次計算的結(jié)果算出最終結(jié)果返回即可，如果將上面的代碼采用這個模式就是下面這個樣子：

采用這個模式之后我們就變回了尾遞歸了，當(dāng)執(zhí)行到基線條件時，直接返回y的值即可。根本不需要回溯到以前。除了利用這種模式，我們還可以利用一種“后繼傳遞模式”，跟累加器傳遞模式一樣也需要修改函數(shù)簽名，增加一個參數(shù)，我們繼續(xù)修改上面這串代碼：

相比累加器傳遞模式，這種方式比較難理解，其實sfunc在到達(dá)基線條件時y就等同于下面這個lambda表達(dá)式：a => a*4*3*2，然后就是調(diào)用y(1)就直接計算最終的結(jié)果了。在簡單點就是y這個函數(shù)被包裝了了好幾層，比如上面這段函數(shù)執(zhí)行結(jié)束時y的調(diào)用順序：

a為1傳遞給y(2 * a)，結(jié)果就是y(2)。

a為2傳遞給y(3 * a)，結(jié)果就是y(6)。

a為6傳遞給y(4 * a)，結(jié)果就是y(24)。

a為24傳遞給x => x，輸出24。

如果還是不理解只能下斷點，調(diào)試自己琢磨琢磨了，實在不懂的可以Q問。

在滿足必要的經(jīng)濟(jì)的條件下,研究更加高深的技術(shù).滿足自己的野心

最新評論