建站
咨詢
售后
建站咨詢
新聞中心
今天，我們來聊聊遞歸函數(shù)。為啥突然想到遞歸?其實就從電影名字《恐怖游輪》《盜夢空間》想到了。
創(chuàng)新互聯(lián)長期為超過千家客戶提供的網(wǎng)站建設(shè)服務(wù)，團隊從業(yè)經(jīng)驗10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為尋甸企業(yè)提供專業(yè)的成都網(wǎng)站建設(shè)、做網(wǎng)站，尋甸網(wǎng)站改版等技術(shù)服務(wù)。擁有十多年豐富建站經(jīng)驗和眾多成功案例,為您定制開發(fā)。
遞歸是啥?
遞歸函數(shù)大家肯定寫過，學(xué)校上課的時候，估計最開始的例子就是斐波拉契數(shù)列了吧。例如：
- int Fibonacci(n) {
- if (n < 2) return n;
- return Fibonacci(n - 1) + Fibonacci(n - 2);
- }
遞歸函數(shù)簡而言之就是在一個函數(shù)中，又“遞歸”調(diào)用自己。在寫遞歸函數(shù)的時候，需要注意的地方就是遞歸函數(shù)的結(jié)束條件。用遞歸函數(shù)確實能簡化很多算法的實現(xiàn)，比如常見的二叉樹遍歷等。但往往在寫遞歸函數(shù)的時候，最容易出現(xiàn)的問題就是所謂的“棧溢出”。
為什么會有“棧溢出”呢?因為函數(shù)調(diào)用的過程，都要借助“棧”這種存儲結(jié)構(gòu)來保存運行時的一些狀態(tài)，比如函數(shù)調(diào)用過程中的變量拷貝，函數(shù)調(diào)用的地址等等。而“?！蓖鎯臻g是有限的，當(dāng)超過其存儲空間后，就會拋出著名的異常/錯誤“StackOverflowError”。
我們以一個簡單的加法為例，例如：
- 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;
很簡答，編譯運行后，比較小的數(shù)字，能得到正確的答案，當(dāng)數(shù)字?jǐn)U大后，就會直接發(fā)生“segmentation fault”。
尾遞歸又是啥?
我得知這個概念，最開始還是因為很多年前一次面試，面試官問我“你知道什么是尾遞歸嗎?”，我以為是“偽”遞歸，難道是假的遞歸???當(dāng)初我也是懵逼狀態(tài)(當(dāng)初面試官忍住沒笑也是厲害了)。從“尾”字可看出來即若函數(shù)在尾巴的地方遞歸調(diào)用自己。上面的例子寫成尾遞歸，就變成了如下：
- int tailsum(int n, int sum) {
- if (n == 0) return sum;
- return tailsum(n-1, sum+n);
- }
可以試試結(jié)果，計算從 1 加到 1000000，仍然是segmentation fault。為什么呢?因為這種寫法，本質(zhì)上還是有多層的函數(shù)嵌套調(diào)用，中間仍然有壓棧、出棧等占用了存儲空間(只不過能比前面的方法會省部分空間)。
尾遞歸優(yōu)化
當(dāng)你給編譯選項開了優(yōu)化之后，見證奇跡的時刻到了，居然能算出正確結(jié)果。如圖所示：
C++ 默認(rèn) segmentation fault， 開啟編譯優(yōu)化后，能正常計算結(jié)果。
原因就是因為編譯器幫助做了尾遞歸優(yōu)化，可以打開匯編代碼看看(這里就不展示 C++的了)。后面我用大家比較熟悉的 JVM based 語言 Scala 來闡述這個優(yōu)化過程。(好像 Java 的編譯器沒做這方面的優(yōu)化，至少我實驗我本地 JDK8 是沒有的，不清楚最新版本的有木有)(scala 本身提供了一個注解幫助編譯器強制校驗是否能夠進(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)化，能夠正確計算出結(jié)果，當(dāng)通過 -g:notailcalls 編譯參數(shù)去掉尾遞歸優(yōu)化后，就發(fā)生了 Exception in thread "main" java.lang.StackOverflowError了。
默認(rèn)啟用尾遞歸優(yōu)化正常計算結(jié)果，禁用尾遞歸優(yōu)化則“StackOverflow”。
我們來看看生成的字節(jié)碼有什么不同。
包含尾遞歸優(yōu)化的字節(jié)碼，直接 goto 循環(huán)。
禁用尾遞歸優(yōu)化的字節(jié)碼，方法調(diào)用。
從上面可以看出，尾遞歸優(yōu)化后，變成循環(huán)了(前面的 C++ 類似)。
好了，尾遞歸咱們就了解到這里。個人看法，我們知道有“尾遞歸”這個點就好了，有時候我們寫遞歸就是為了方便，代碼可讀性好，如果確實是出于性能考慮，我們可以自己用迭代的方式去實現(xiàn)，不依賴于具體的編譯器實現(xiàn)。當(dāng)然對于像 scala 這樣，有一些語法糖能夠幫助校驗和驗證，也是一個不錯的選擇。但遞歸轉(zhuǎn)迭代的能力，我們能具備豈不更好。
本文轉(zhuǎn)載自微信公眾號「 程序猿石頭」，可以通過以上二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系 程序猿石頭公眾號。
本文名稱：大家都知道遞歸，尾遞歸呢？什么又是尾遞歸優(yōu)化？
本文來源：http://www.dlmjj.cn/article/dhijdeg.html
