大家都知道遞歸,尾遞歸呢?什么又是尾遞歸優(yōu)化?

來(lái)源：程序猿石頭

作者：碼農(nóng)唐磊

今天，我們來(lái)聊聊遞歸函數(shù)。為啥突然想到遞歸？其實(shí)就從電影名字《恐怖游輪》《盜夢(mèng)空間》想到了。

遞歸是啥？

遞歸函數(shù)大家肯定寫過，學(xué)校上課的時(shí)候，估計(jì)最開始的例子就是斐波拉契數(shù)列了吧。例如：

int?Fibonacci(n)?{
????if?(n < 2) return?n;
????return?Fibonacci(n - 1) + Fibonacci(n - 2);
}

遞歸函數(shù)簡(jiǎn)而言之就是在一個(gè)函數(shù)中，又“遞歸”調(diào)用自己。在寫遞歸函數(shù)的時(shí)候，需要注意的地方就是遞歸函數(shù)的結(jié)束條件。用遞歸函數(shù)確實(shí)能簡(jiǎn)化很多算法的實(shí)現(xiàn)，比如常見的二叉樹遍歷等。但往往在寫遞歸函數(shù)的時(shí)候，最容易出現(xiàn)的問題就是所謂的“棧溢出”。

為什么會(huì)有“棧溢出”呢？因?yàn)楹瘮?shù)調(diào)用的過程，都要借助“?！边@種存儲(chǔ)結(jié)構(gòu)來(lái)保存運(yùn)行時(shí)的一些狀態(tài)，比如函數(shù)調(diào)用過程中的變量拷貝，函數(shù)調(diào)用的地址等等。而“棧”往往存儲(chǔ)空間是有限的，當(dāng)超過其存儲(chǔ)空間后，就會(huì)拋出著名的異常/錯(cuò)誤“StackOverflowError”。

我們以一個(gè)簡(jiǎn)單的加法為例，例如：

int?sum(int?n)?{
????if?(n <= 1) return?n;
????return?n + sum(n-1);
}

std::cout?<< sum(100) << std::endl;
std::cout?<< sum(1000000) << std::endl;

很簡(jiǎn)答，編譯運(yùn)行后，比較小的數(shù)字，能得到正確的答案，當(dāng)數(shù)字?jǐn)U大后，就會(huì)直接發(fā)生“segmentation fault”。

尾遞歸又是啥？

我得知這個(gè)概念，最開始還是因?yàn)楹芏嗄昵耙淮蚊嬖?，面試官問我“你知道什么是尾遞歸嗎？”，我以為是“偽”遞歸，難道是假的遞歸？？？當(dāng)初我也是懵逼狀態(tài)（當(dāng)初面試官忍住沒笑也是厲害了）。從“尾”字可看出來(lái)即若函數(shù)在尾巴的地方遞歸調(diào)用自己。上面的例子寫成尾遞歸，就變成了如下：

int?tailsum(int?n, int?sum)?{
????if?(n == 0) return?sum;
????return?tailsum(n-1, sum+n);
}

可以試試結(jié)果，計(jì)算從 1 加到 1000000，仍然是segmentation fault。為什么呢？因?yàn)檫@種寫法，本質(zhì)上還是有多層的函數(shù)嵌套調(diào)用，中間仍然有壓棧、出棧等占用了存儲(chǔ)空間（只不過能比前面的方法會(huì)省部分空間）。

尾遞歸優(yōu)化

當(dāng)你給編譯選項(xiàng)開了優(yōu)化之后，見證奇跡的時(shí)刻到了，居然能算出正確結(jié)果。如圖所示：

C++?默認(rèn) segmentation fault， 開啟編譯優(yōu)化后，能正常計(jì)算結(jié)果。

原因就是因?yàn)榫幾g器幫助做了尾遞歸優(yōu)化，可以打開匯編代碼看看（這里就不展示 C++的了）。后面我用大家比較熟悉的 JVM based 語(yǔ)言 Scala 來(lái)闡述這個(gè)優(yōu)化過程。(好像 Java 的編譯器沒做這方面的優(yōu)化，至少我實(shí)驗(yàn)我本地 JDK8 是沒有的，不清楚最新版本的有木有)（scala 本身提供了一個(gè)注解幫助編譯器強(qiáng)制校驗(yàn)是否能夠進(jìn)行尾遞歸優(yōu)化@tailrec）

object TailRecObject {

???def?tailSum(n:?Int, sum:?Int): Int = {
????????if?(n == 0) return?sum;
????????return?tailSum(n-1, n+sum);
???}

???def?main(args:?Array[String])?{
??????println(tailSum(100, 0))
??????println(tailSum(1000000, 0))
???}

}

結(jié)果如下圖所示，默認(rèn)情況下?scalac?做了尾遞歸優(yōu)化，能夠正確計(jì)算出結(jié)果，當(dāng)通過?-g:notailcalls?編譯參數(shù)去掉尾遞歸優(yōu)化后，就發(fā)生了?Exception in thread "main" java.lang.StackOverflowError了。

默認(rèn)啟用尾遞歸優(yōu)化正常計(jì)算結(jié)果，禁用尾遞歸優(yōu)化則“StackOverflow”。

我們來(lái)看看生成的字節(jié)碼有什么不同。

包含尾遞歸優(yōu)化的字節(jié)碼，直接 goto 循環(huán)。

禁用尾遞歸優(yōu)化的字節(jié)碼，方法調(diào)用。

從上面可以看出，尾遞歸優(yōu)化后，變成循環(huán)了（前面的 C++ 類似）。

好了，尾遞歸咱們就了解到這里。個(gè)人看法，我們知道有“尾遞歸”這個(gè)點(diǎn)就好了，有時(shí)候我們寫遞歸就是為了方便，代碼可讀性好，如果確實(shí)是出于性能考慮，我們可以自己用迭代的方式去實(shí)現(xiàn)，不依賴于具體的編譯器實(shí)現(xiàn)。當(dāng)然對(duì)于像 scala 這樣，有一些語(yǔ)法糖能夠幫助校驗(yàn)和驗(yàn)證，也是一個(gè)不錯(cuò)的選擇。但遞歸轉(zhuǎn)迭代的能力，我們能具備豈不更好。