2023學(xué)年完整公開(kāi)課版197python遞歸函數(shù)

python-遞歸函數(shù)2任務(wù)描述華云數(shù)據(jù)集團(tuán)基于CloudUltra?私有云為兵工物資集團(tuán)構(gòu)建私有云平臺(tái)，在保障平臺(tái)的高可靠性、高可用性、高安全性的基礎(chǔ)之上，為兵工物資集團(tuán)提供持續(xù)性、可擴(kuò)展性、可管理性的服務(wù)。和傳統(tǒng)模式相比基礎(chǔ)設(shè)施使用率提高了75%以上，數(shù)據(jù)可靠性提高到了99.9%，保證兵工物資集團(tuán)數(shù)據(jù)安全可控，滿足集團(tuán)業(yè)務(wù)需求。本節(jié)主要講解兵工物資集團(tuán)構(gòu)建私有云平臺(tái)項(xiàng)目的實(shí)施過(guò)程中，對(duì)python-遞歸函數(shù)的介紹。目錄遞歸函數(shù)小結(jié)34遞歸函數(shù)在函數(shù)內(nèi)部，可以調(diào)用其他函數(shù)。如果一個(gè)函數(shù)在內(nèi)部調(diào)用自身本身，這個(gè)函數(shù)就是遞歸函數(shù)。舉個(gè)例子，我們來(lái)計(jì)算階乘n!=1x2x3x...xn，用函數(shù)fact(n)表示，可以看出：fact(n)=n!=1x2x3x...x(n-1)xn=(n-1)!xn=fact(n-1)xn所以，fact(n)可以表示為nxfact(n-1)，只有n=1時(shí)需要特殊處理。5遞歸函數(shù)于是，fact(n)用遞歸的方式寫(xiě)出來(lái)就是：deffact(n):ifn==1:return1returnn*fact(n-1)6遞歸函數(shù)上面就是一個(gè)遞歸函數(shù)?？梢栽囋嚕?gt;>>fact(1)1>>>fact(5)120>>>fact(100)93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000L7遞歸函數(shù)如果我們計(jì)算fact(5)，可以根據(jù)函數(shù)定義看到計(jì)算過(guò)程如下：===>fact(5)===>5*fact(4)===>5*(4*fact(3))===>5*(4*(3*fact(2)))===>5*(4*(3*(2*fact(1))))===>5*(4*(3*(2*1)))===>5*(4*(3*2))===>5*(4*6)===>5*24===>1208遞歸函數(shù)的優(yōu)點(diǎn)是定義簡(jiǎn)單，邏輯清晰。理論上，所有的遞歸函數(shù)都可以寫(xiě)成循環(huán)的方式，但循環(huán)的邏輯不如遞歸清晰。使用遞歸函數(shù)需要注意防止棧溢出。在計(jì)算機(jī)中，函數(shù)調(diào)用是通過(guò)棧（stack）這種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的，每當(dāng)進(jìn)入一個(gè)函數(shù)調(diào)用，棧就會(huì)加一層棧幀，每當(dāng)函數(shù)返回，棧就會(huì)減一層棧幀。由于棧的大小不是無(wú)限的，所以，遞歸調(diào)用的次數(shù)過(guò)多，會(huì)導(dǎo)致棧溢出。可以試試fact(1000)：>>>fact(1000)Traceback(mostrecentcalllast):File"<stdin>",line1,in<module>File"<stdin>",line4,infact...File"<stdin>",line4,infactRuntimeError:maximumrecursiondepthexceeded遞歸函數(shù)9解決遞歸調(diào)用棧溢出的方法是通過(guò)尾遞歸優(yōu)化，事實(shí)上尾遞歸和循環(huán)的效果是一樣的，所以，把循環(huán)看成是一種特殊的尾遞歸函數(shù)也是可以的。尾遞歸是指，在函數(shù)返回的時(shí)候，調(diào)用自身本身，并且，return語(yǔ)句不能包含表達(dá)式。這樣，編譯器或者解釋器就可以把尾遞歸做優(yōu)化，使遞歸本身無(wú)論調(diào)用多少次，都只占用一個(gè)棧幀，不會(huì)出現(xiàn)棧溢出的情況。遞歸函數(shù)10上面的fact(n)函數(shù)由于returnn*fact(n-1)引入了乘法表達(dá)式，所以就不是尾遞歸了。要改成尾遞歸方式，需要多一點(diǎn)代碼，主要是要把每一步的乘積傳入到遞歸函數(shù)中：deffact(n):returnfact_iter(n,1)deffact_iter(num,product):ifnum==1:returnproductreturnfact_iter(num-1,num*product)遞歸函數(shù)11遞歸函數(shù)可以看到，returnfact_iter(num-1,num*product)僅返回遞歸函數(shù)本身，num-1和num*product在函數(shù)調(diào)用前就會(huì)被計(jì)算，不影響函數(shù)調(diào)用。fact(5)對(duì)應(yīng)的fact_iter(5,1)的調(diào)用如下：===>fact_iter(5,1)===>fact_iter(4,5)===>fact_iter(3,20)===>fact_iter(2,60)===>fact_iter(1,120)===>12012遞歸函數(shù)尾遞歸調(diào)用時(shí)，如果做了優(yōu)化，棧不會(huì)增長(zhǎng)，因此，無(wú)論多少次調(diào)用也不會(huì)導(dǎo)致棧溢出。遺憾的是，大多數(shù)編程語(yǔ)言沒(méi)有針對(duì)尾遞歸做優(yōu)化，Python解釋器也沒(méi)有做優(yōu)化，所以，即使把上面的fact(n)函數(shù)改成尾遞歸方式，也會(huì)導(dǎo)致棧溢出。13小結(jié)使用遞歸函數(shù)的優(yōu)點(diǎn)是邏輯簡(jiǎn)單清晰，缺點(diǎn)是過(guò)