【python】 深入理解遞歸思想

一、遞歸定義

遞歸就是子程序（或函數(shù)）直接調(diào)用自己或通過(guò)一系列調(diào)用語(yǔ)句間接調(diào)用自己，是一種描述問(wèn)題和解決問(wèn)題的基本方法。遞歸常用來(lái)解決結(jié)構(gòu)相似的問(wèn)題。所謂結(jié)構(gòu)相似，是指構(gòu)成原問(wèn)題的子問(wèn)題與原問(wèn)題在結(jié)構(gòu)上相似，可以用類似的方法解決。具體地，整個(gè)問(wèn)題的解決，可以分為兩部分：第一部分是一些特殊情況，有直接的解法；第二部分與原問(wèn)題相似，但比原問(wèn)題的規(guī)模小，并且依賴第一部分的結(jié)果。實(shí)際上，遞歸是把一個(gè)不能或不好解決的大問(wèn)題轉(zhuǎn)化成一個(gè)或幾個(gè)小問(wèn)題，再把這些小問(wèn)題進(jìn)一步分解成更小的小問(wèn)題，直至每個(gè)小問(wèn)題都可以直接解決。

基本要素:

基線條件：確定遞歸到何時(shí)終止，函數(shù)不再調(diào)用自己，也稱為遞歸出口；

遞歸條件：函數(shù)調(diào)用自己，將大問(wèn)題分解為類似的小問(wèn)題，也稱為遞歸體。

核心思想:

每一次遞歸，整體問(wèn)題都要比原來(lái)減小，并且遞歸到一定層次時(shí)，要能直接給出結(jié)果。

def foo(n): if n = 1: return 1 return foo(n-1)

上面就實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的遞歸函數(shù)。

同時(shí)需要注意:使用遞歸函數(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)致棧溢出。會(huì)報(bào)錯(cuò)：`RecursionError: maximum recursion depth exceeded in comparison

二、遞歸思想

遞歸算法常用來(lái)解決結(jié)構(gòu)相似的問(wèn)題。

所謂結(jié)構(gòu)相似，是指構(gòu)成原問(wèn)題的子問(wèn)題與原問(wèn)題在結(jié)構(gòu)上相似，可以用類似的方法解決。具體地，整個(gè)問(wèn)題的解決，可以分為兩部分：第一部分是一些特殊情況，有直接的解法；第二部分與原問(wèn)題相似，但比原問(wèn)題的規(guī)模小，并且依賴第一部分的結(jié)果。

本質(zhì)上，遞歸是把一個(gè)不能或不好解決的大問(wèn)題轉(zhuǎn)化成一個(gè)或幾個(gè)小問(wèn)題，再把這些小問(wèn)題進(jìn)一步分解成更小的問(wèn)題，直至每個(gè)小問(wèn)題都可以直接解決。

實(shí)際上，遞歸會(huì)將前面所有調(diào)用的函數(shù)暫時(shí)掛起，直到遞歸終止條件給出明確的結(jié)果后，才會(huì)將所有掛起的內(nèi)容進(jìn)行反向計(jì)算。其實(shí)，遞歸也可以看作是一種反向計(jì)算的過(guò)程，前面調(diào)用遞歸的過(guò)程只是將表達(dá)式羅列出來(lái)，待終止條件出現(xiàn)后，才依次從后向前倒序計(jì)算前面掛起的內(nèi)容，最后將所有的結(jié)果一起返回。

三、構(gòu)建函數(shù)

基線條件(base case)：

遞歸程序的最底層位置，在此位置時(shí)沒(méi)有必要再進(jìn)行操作，可以直接返回一個(gè)結(jié)果；

所有遞歸程序都必須至少擁有一個(gè)基線條件，而且必須確保它們最終會(huì)達(dá)到某個(gè)基線條件；否則，程序?qū)⒂肋h(yuǎn)運(yùn)行下去，直到程序缺少內(nèi)存或者?？臻g；

基本結(jié)構(gòu)

至少一個(gè)基線條件：通常在遞歸函數(shù)的開始位置，就設(shè)置基線條件；

一系列的規(guī)則：使得每次調(diào)用遞歸函數(shù)，都趨近于直至達(dá)到基線條件。

思想：

1.找到當(dāng)前這個(gè)值與上一個(gè)值的關(guān)系

2.找到程序的出口 有個(gè)明確的結(jié)束條件

3.假設(shè)當(dāng)前功能已經(jīng)完成 每次進(jìn)入更深一層遞歸時(shí)，問(wèn)題規(guī)模相比上次遞歸都應(yīng)有所減少

遞歸思路：

（1）找重復(fù)：看哪一部分是 實(shí)現(xiàn)函數(shù)的變化；每次進(jìn)入更深一層遞歸時(shí)，問(wèn)題規(guī)模相比上次遞歸都應(yīng)有所減少

（2）找變化：變化的量應(yīng)該作為參數(shù)

（3）找邊界（出口）：終止條件

遞歸可以分為：

（1）直接量+小規(guī)模子問(wèn)題

（2）多個(gè)小規(guī)模子問(wèn)題

（3） “切蛋糕”思維

（4）找遞推公式，等價(jià)交換公式

四、遞歸剖析

首先“遞歸”包括兩個(gè)過(guò)程：遞“去”的過(guò)程，“歸”回的過(guò)程！先從一個(gè)簡(jiǎn)單的遞歸函數(shù)講起

def digui(n): print(n, '<===1===>') if n>0: digui(n-1) print(n, '<===2===>') digui(5) # 5 <===1===> # 4 <===1===> # 3 <===1===> # 2 <===1===> # 1 <===1===> # 0 <===1===> # 0 <===2===> # 1 <===2===> # 2 <===2===> # 3 <===2===> # 4 <===2===> # 5 <===2===>

重點(diǎn)來(lái)理解下，首先是一，看上面的列子，例子中沒(méi)有return，但是不斷的調(diào)用后，最終還是停止了，因?yàn)樽詈髇=0時(shí)，di_gi(0)還是去調(diào)用，從上往下執(zhí)行時(shí)，遇到if n>0 它被終止了，走不下去了，表明，自己能到達(dá)的這層空間已經(jīng)全部執(zhí)行完畢；接下來(lái)請(qǐng)?jiān)胤祷匕?，返回到哪里？返回到函?shù)的調(diào)用者，好我們返回到 di_gui(0)，把“到內(nèi)部調(diào)用函數(shù)” 以下的代碼全部執(zhí)行完；執(zhí)行完，看代碼走到末尾，以為走出了最外層函數(shù)？注意了，此時(shí)它所處的空間并不是最外層哦，因?yàn)橹八徽{(diào)用就在空間里面，所以回到的是 di_gui(1)的這一層空間，現(xiàn)在才是真正的開始“回”，所以繼續(xù)把di_gui(1)的這一層空間，“到內(nèi)部調(diào)用函數(shù)”以下的代碼全部執(zhí)行完，回到di_gui(2)的這一層空間…直到到達(dá)最開始 從外部調(diào)用，讓參數(shù)5進(jìn)入的最外層空間位置，才走出來(lái)！

從內(nèi)存角度（本質(zhì)）來(lái)分析：每調(diào)用一次函數(shù)，都會(huì)單獨(dú)開辟一份棧幀空間，遞歸函數(shù)就是不停的開辟和釋放棧幀空間的過(guò)程，具體來(lái)理解下：一個(gè)普通函數(shù)從執(zhí)行到結(jié)束，就是一個(gè)開辟空間和釋放空間的過(guò)程；而遞歸函數(shù)是在調(diào)用最外層函數(shù)時(shí)，先開辟一個(gè)最外層空間，每調(diào)用一次自身，就會(huì)在最外層空間內(nèi)，再自己開辟本次的空間（所以遞歸耗內(nèi)存）（還有一種說(shuō)法是，不斷的本次空間的基礎(chǔ)上再開辟空間，等于是不斷的嵌套，其實(shí)這兩種說(shuō)法本質(zhì)上是一樣的，因?yàn)樾畔⒍伎梢宰龅讲还蚕恚?，空間之間如果不通過(guò)參數(shù)傳遞或者用return 返回值，信息是不共享的

遞歸的執(zhí)行過(guò)程：首先，遞歸會(huì)執(zhí)行“去”的過(guò)程，只需要滿足終止條件，就會(huì)一直在函數(shù)內(nèi)，帶著更新的參數(shù)，調(diào)用函數(shù)自身，注意：到內(nèi)部調(diào)用函數(shù)， 以下面的代碼不會(huì)被執(zhí)行，而是暫停阻塞；此時(shí) 隨著函數(shù)每調(diào)用一次自身，還沒(méi)有觸發(fā) 返回值和到達(dá)終止條件，等同于在原來(lái)的基礎(chǔ)上不斷“向下/向內(nèi)”開辟新的內(nèi)存空間，記住，每次調(diào)用一次函數(shù)，就不是處在同一空間

去的過(guò)程：就是不斷的開辟空間，在回的過(guò)程，不停的釋放空間，遞歸函數(shù)就是不停的開辟和釋放空間的過(guò)程

回的過(guò)程：最后一層空間所有代碼執(zhí)行完畢，就會(huì)觸發(fā)回的過(guò)程，或者遇到return也會(huì)觸發(fā)回的過(guò)程，回到上一層函數(shù)調(diào)用的位置

“遞”去的過(guò)程結(jié)束有兩種情況?一是：當(dāng)前這層空間函數(shù)全部執(zhí)行結(jié)束（終止條件），二是：執(zhí)行到了return 返回值，直接返回；

每一層遞歸空間都是獨(dú)立的個(gè)體，獨(dú)立的副本，資源不共享

五、尾遞歸優(yōu)化

在計(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ò)多時(shí)，可能會(huì)導(dǎo)致棧溢出；

尾遞歸：指函數(shù)返回時(shí)調(diào)用自身本身，并且return語(yǔ)句不能包含表達(dá)式。這樣，編譯器或者解釋器就可以把尾遞歸做優(yōu)化，使遞歸本身無(wú)論調(diào)用多少次，都只占用一個(gè)棧幀，不會(huì)出現(xiàn)棧溢出的情況；

尾遞歸和循環(huán)的效果是一樣的，實(shí)際上，可以把循環(huán)看成是一種特殊的尾遞歸函數(shù)；

尾遞歸是優(yōu)化遞歸防止溢出的一種方法，但并不能徹底解決溢出。舉個(gè)形象的例子：開車減速慢行可以少出車禍，但減速慢行不一定不出車禍；

階乘的fact(n)函數(shù)，return語(yǔ)句，返回了n * fact(n - 1)的乘法表達(dá)式，不是尾遞歸。要改成尾遞歸方式，需要把每一步的乘積傳入到遞歸函數(shù)中。

參考代碼如下：

def factorial(n): return fact_iter(n, 1) def fact_iter(n, product): if n == 1: return product return fact_iter(n - 1, n * product) print(factorial(5)) 120

將每次的乘積，存入到 product 中，return fact_iter(n-1, n * product) 返回的僅僅是函數(shù)本身，n - 1 和 n * product 在函數(shù)調(diào)用前就會(huì)被計(jì)算出來(lái)，不影響函數(shù)調(diào)用；

優(yōu)化的實(shí)質(zhì)，就是將原本倒序的計(jì)算，通過(guò) n * product 變?yōu)榱苏虻挠?jì)算，還是遞歸的思想，但是不會(huì)占用其他的棧幀，因?yàn)樗械慕Y(jié)果都已近存放在了 product 中。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) ===> 120

尾遞歸調(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)化，任何遞歸函數(shù)都存在棧溢出的問(wèn)題。所以，即使把上面的fact(n)函數(shù)改成尾遞歸方式，也可能導(dǎo)致棧溢出。

六.遞歸實(shí)例

斐波拉契數(shù)列

數(shù)列：規(guī)定F(0) = 0，F(xiàn)(1) = 1，從第三項(xiàng)起，每一項(xiàng)都等于前兩項(xiàng)的和，即F(N) = F(N - 1) + F(N - 2) (N >= 2)

參考代碼

def fibonacci(n): if n < 2: return n return fibonacci(n-1) + fibonacci(n-2) print(fibonacci(10)) 55

n項(xiàng)指定值之和

s = a * 1 + a * 2 + a * 3 + a * 4 + ...... + a * n，SSS(a, n) = SSS(a, n-1) + a * n

參考代碼

def n_sum(a, n): if n == 1: return a return n_sum(a, n - 1) + n * a print(n_sum(2, 5)) 30

快速排序

原理：基于分治策略，設(shè)定一個(gè)基準(zhǔn)線(pivot)，將數(shù)據(jù)與基準(zhǔn)線對(duì)比，分成大于和小于兩部分，通過(guò)遞歸，不斷分治實(shí)現(xiàn)數(shù)據(jù)的排序；

參考代碼

def quick_sort(n): if len(n) < 2: return n else: pivot = n[0] left = [x for x in n[1:] if x < pivot] right = [x for x in n[1:] if x > pivot] return quick_sort(left) + [x for x in n if x == n[0]] + quick_sort(right) print(quick_sort([5,11,3,5,8,2,6,7,3])) [2, 3, 3, 5, 5, 6, 7, 8, 11]

漢諾塔問(wèn)題

把問(wèn)題理解為三步：第一步，將n-1個(gè)塔從A移動(dòng)到B（中間使用到了C）；第二步，將第n個(gè)塔從A移動(dòng)到C；第三步，將n-1個(gè)塔從B移動(dòng)到C（中間用到了A）

參考代碼

N = 0 def hannoi(n,a,b,c): global N if n>0: hannoi(n-1, a, c, b) N = N + 1 print('第{}次移動(dòng)： move from {} to {}'.format(N, a, c)) hannoi(n-1, b, a, c)

五、遞歸應(yīng)用

遞歸算法一般用于解決三類問(wèn)題

數(shù)據(jù)的定義是按遞歸定義的，比如：Fibonacci函數(shù)、階乘等；

問(wèn)題的解法是按遞歸算法實(shí)現(xiàn)的，比如：回溯法；

數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的，比如：樹的遍歷、圖的搜索等；

優(yōu)點(diǎn)

遞歸使代碼看起來(lái)更加整潔、優(yōu)雅；

遞歸可以將復(fù)雜任務(wù)分解成更簡(jiǎn)單的子問(wèn)題；

使用遞歸比使用一些嵌套迭代更容易解決問(wèn)題。

缺點(diǎn)

遞歸的邏輯很難調(diào)試、跟進(jìn)；

遞歸的運(yùn)行效率較低。因?yàn)樵谶f歸的調(diào)用過(guò)程中，系統(tǒng)會(huì)為每一層的返回值或局部變量開辟新的棧進(jìn)行存儲(chǔ)。遞歸次數(shù)過(guò)多容易造成棧溢出。

GUI Python

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。