您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“什么是python尾遞歸”,感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷,實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“什么是python尾遞歸”吧!
遞歸是啥?
遞歸函數(shù)大家肯定寫過(guò),學(xué)校上課的時(shí)候,估計(jì)最開(kāi)始的例子就是斐波拉契數(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),比如常見(jiàn)的二叉樹(shù)遍歷等。但往往在寫遞歸函數(shù)的時(shí)候,最容易出現(xiàn)的問(wèn)題就是所謂的“棧溢出”。
為什么會(huì)有“棧溢出”呢?因?yàn)楹瘮?shù)調(diào)用的過(guò)程,都要借助“?!边@種存儲(chǔ)結(jié)構(gòu)來(lái)保存運(yùn)行時(shí)的一些狀態(tài),比如函數(shù)調(diào)用過(guò)程中的變量拷貝,函數(shù)調(diào)用的地址等等。而“棧”往往存儲(chǔ)空間是有限的,當(dāng)超過(guò)其存儲(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è)概念,最開(kāi)始還是因?yàn)楹芏嗄昵耙淮蚊嬖?,面試官?wèn)我“你知道什么是尾遞歸嗎?”,我以為是“偽”遞歸,難道是假的遞歸???當(dāng)初我也是懵逼狀態(tài)(當(dāng)初面試官忍住沒(méi)笑也是厲害了)。從“尾”字可看出來(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ǔ)空間(只不過(guò)能比前面的方法會(huì)省部分空間)。
尾遞歸優(yōu)化
當(dāng)你給編譯選項(xiàng)開(kāi)了優(yōu)化之后,見(jiàn)證奇跡的時(shí)刻到了,居然能算出正確結(jié)果。如圖所示:
C++ 默認(rèn) segmentation fault, 開(kāi)啟編譯優(yōu)化后,能正常計(jì)算結(jié)果。
原因就是因?yàn)榫幾g器幫助做了尾遞歸優(yōu)化,可以打開(kāi)匯編代碼看看(這里就不展示 C++的了)。后面我用大家比較熟悉的 JVM based 語(yǔ)言 Scala 來(lái)闡述這個(gè)優(yōu)化過(guò)程。(好像 Java 的編譯器沒(méi)做這方面的優(yōu)化,至少我實(shí)驗(yàn)我本地 JDK8 是沒(méi)有的,不清楚最新版本的有木有)(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)通過(guò) -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++ 類似)。
到此,相信大家對(duì)“什么是python尾遞歸”有了更深的了解,不妨來(lái)實(shí)際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。