Python实现递归算法
遞歸概念
任何可以用計算機求解的問題所需的計算時間都與其規模有關,問題的規模越小,解題所需的計算時間往往也越短,從而比較容易處理。直接或者間接調用自身的算法稱為遞歸算法,用函數自身給出定義的函數稱為遞歸函數。使用遞歸技術往往使函數的定義和算法的描述簡捷且易于理解,有些數據結構,如二叉樹等,由于其本身固有的遞歸特性,特別適合用遞歸的形式來描述。
當我們設計遞歸算法時,應滿足三點:①符合遞歸的描述:需要解決的問題可以化為子問題求解,而子問題求解的方法與原問題相同,只是數量增大或減少;②遞歸調用的次數是有限的;③必須有遞歸結束的條件
其中第③點是我們在編寫遞歸函數時必須要注意的,一定要有遞歸結束條件,即每個遞歸函數都必須有非遞歸定義的初始值,在函數遞歸結束條件下,沒有再調用遞歸函數。
if (滿足遞歸結束條件):這個程序塊中沒有調用遞歸函數的語句函數遞歸的調用機制
遞歸函數調用同樣遵守函數調用機制,當函數調用自己時也要將函數狀態、返回地址、函數參數、局部變量壓入棧中進行保存。
實際上函數被調用時執行的代碼是函數的一個副本,與調用函數的代碼無關。當一個函數被調用兩次,則函數就會有兩個副本在內存中運行,每個副本都有自己的棧空間且與調用函數的棧空間不同,因此不會相互影響。這種調用機制決定了函數是可以遞歸調用的。
當有多個算法構成嵌套調用的時候,按照后調用先返回的原則進行,算法之間的信息傳遞和控制轉移必須通過棧來實現,即系統將整個程序運行時所需的數據空間安排在一個棧中,每調用一個算法,就為它在棧頂分配一個存儲區,每退出一個算法,就釋放它在棧頂的存儲區,當前運行算法的數據一定是在棧頂的。
遞歸算法的優缺點
遞歸算法結構清晰,可讀性強,并且容易用數學歸納證明算法的正確性,為設計算法和調試程序帶來很大的方便。但是遞歸調用運行效率比較低,無論是計算時間還是占用的存儲空間都比非遞歸算法要多。
有時希望在遞歸算法中消除遞歸調用,使其轉化為一個非遞歸算法。通常采用的方法是,用一個用戶的棧來模擬系統的遞歸調用工作棧,從而達到將遞歸算法改為非遞歸算法的目的。
算法實例
階乘函數
我們首先通過階乘函數來了解遞歸,我們可以很容易的將階乘函數的遞歸公式寫出來:
我們通過這個遞歸公式,可以很容易的寫出計算階乘的遞歸函數
#階乘問題 def factorial(n:int): '''n為輸入,為n!''' if n == 0: return 1 else: return n*factorial(n-1)#時間復雜度為O(n)可以發現,我們在寫遞歸函數的時候,很大程度上依賴于我們根據階乘這個具體問題總結出來的遞歸公式,根據遞歸公式可以很容易的寫出對應的遞歸函數。
Fabonacci數列
學過數學的人應該都知道Fabonacci數列,1,1,2,3,5,8,13…,我們可以很容易的寫出這個數列的遞歸公式表示
同樣的,根據這個遞歸公式我們就可以方便的寫出遞歸函數
#Fabonacci數列 def fabonacci(n:int): '''n為輸出fabonacci數列的第多少個''' if n <= 1: return 1 else: return fabonacci(n-1)+fabonacci(n-2)#時間復雜度為O(2^n)??調用過程類比二叉樹全排列問題
求解一個無重復元素數組的全排列,即list中所有元素需要考慮順序問題的全部可能的排列。比如[1,2,3],它的全排列是 123,132,213,231,312,321,它的個數為len(list)!
我們根據上面的兩個問題的思路,我們這里也要根據全排列問題,總結出來一個遞歸公式。我們記數組R[r_1,r_2,r_3,…]的長度為n,記P(R)為數組R的全排列,記R_i=R-[r_i],記r_iP(R_i)表示在全排列P(R_i)的每一個排列前加上前綴r_i得到的排列組合。
當n=1時,我們可以得到P(R) = R = [r] ,數組R中只有r一個元素,自然也就只有一種排列。
當n>1時,我們可以寫出P(R) = r_1P(r_1)+r_2P(r_2)+…+r_nP(r_n)
上面的關系實際上給出了計算P(R)的遞歸公式如下:
既然總結出了全排列問題的遞歸公式,我們接下來就可以寫出具體的遞歸函數
#組合全排列問題 def swap(s:list,m:int,k:int): '''交換數組s中指定位置m,k處的兩個字符'''s_ = s.copy() #切記不可以直接使用 s_ = s,否則修改s_會直接影響到s,因為使用s_ = s時,是將s_指向s所指向的數組首地址,這樣其實s_和s指向的是同一個數組。temp = s_[m]s_[m] = s_[k]s_[k] = temp return s_def perm(s:str): '''s為輸入的list'''result = [''] #每次函數調用完返回的中間數組result_ = [] #臨時輔助數組string = '' #臨時輔助空字符串if len(s) < 1: return [''] elif len(s) == 1: return s else: for i in range(len(s)):str_ = swap(s,0,i) for j in perm(str_[1:]): #獲得riP(ri),其中perm(str_[1:])獲得的是P(ri)string = s[i]+j for w in result:result_.append(w+string) #更新listresult = result_ #這里可以直接使用 = ,是因為下面result_指向了【】,而result并沒有改變result_ = [] return result整數劃分問題
正整數可以表示為一系列的正整數之和,例如:
n = n_1 + n_2 + n_3 + … + n_k ?(其中n_1>=n_2>=…>=n_k>=1)
我們目的是對于一個正整數n,到底有多少條符合條件的劃分
我們考慮能不能把問題分解,使問題的規模變小,這里我們引入一個中間變量m,對于正整數n,將可能的劃分中最大加數n_1不大于m的劃分個數記為q(n,m)。
那么我們很容易就能得到,當 m = 1 ?或者 n = 1 的時候,q(n,m) = 1, m=1時即n_i全為1,自然也就只有一種情況。
當 n=m 的時候,劃分可以由 n_1 = n 的劃分 和 n_1<=n-1 的劃分組成 ,即q(n,m)=q(n,n)=1+q(n,n-1)
當 n < m 的時候,n_1 <= n < m ,則q(n,m) = q(n,n)
當 n > m 的時候,劃分可以由n_1 = m的劃分 和n_1<=m-1的劃分組成,這個時候q(n,m) = q(n-m,m) + q(n,m-1)
根據上面的關系得到q(n,m)的遞歸公式如下
所以整數劃分的遞歸函數可以寫成下面這個樣子
#整數劃分問題 def q(n:int,m:int): if n < 1 or m < 1: return 0 if n == 1 or m == 1: return 1 if n == m: return 1 + q(n,n-1) if n > m : return q(n,m-1) + q(n-m,m) if n < m:return?q(n,n)hanoi問題
下面是遞歸算法中最著名的漢諾塔問題,想必大家在最初學習遞歸算法的時候肯定被折磨過很多次,這里我們試著能不能像上面的問題一樣,總結出一個遞歸公式,或者得到一個遞歸流程。
比如要將a上面的盤子轉移到b上面,當a上面只有一個盤子的時候,直接a->b,如果a上面有兩個盤子,步驟是a->c,a->b,c->b,那當我們變成三個盤子的時候,我們還像這樣寫出我們的步驟:a->b,a->c,b->c,a->b,c->a,c->b,a->b。
從上面我們的步驟中可以發現,我們要將a上面的n個盤子放到b上面,我們應該首先將n-1個盤子放到c上面,然后a->b,再將c上面的n-1個盤子,轉移到b上。那么n-1個盤子放到c上面,首先應該將n-2個盤子放到b上面,然后a->c,再將b上面的n-2個盤子放到c上,接下來循環往復… 我們可以驚人的發現,這不就是遞歸的思想了嗎,那整個hanoi的問題就可以簡單的描述為:
可以很快的寫出來hanoi的遞歸函數了:
#漢諾塔問題 def hanoi(n:int,a:str,b:str,c:str): if n < 1:print('input error!') if n == 1:print(a+'-->'+b) else:hanoi(n-1,a,c,b)print(a+'-->'+b)hanoi(n-1,c,b,a)個人博客:https://blog.csdn.net/Pual_wang/article/details/100604688
參考內容
計算機算法設計與分析(第四版) 王曉東著
https://www.cnblogs.com/king-lps/p/10748535.html
https://www.cnblogs.com/xiaoyunoo/p/3519577.html
人生不易,且行且珍惜
機器學習初學者
黃海廣博士創建的公眾號,黃海廣博士個人知乎粉絲21000+,github排名全球前120名(30000+)。本公眾號致力于人工智能方向的科普性文章,為初學者提供學習路線和基礎資料。原創作品有:吳恩達機器學習個人筆記、吳恩達深度學習筆記等。
往期精彩回顧
那些年做的學術公益-你不是一個人在戰斗
良心推薦:機器學習入門資料匯總及學習建議
吳恩達機器學習課程筆記及資源(github標星12000+,提供百度云鏡像)
吳恩達深度學習筆記及視頻等資源(github標星8500+,提供百度云鏡像)
《統計學習方法》的python代碼實現(github標星7200+)
精心整理和翻譯的機器學習的相關數學資料
首發:深度學習入門寶典-《python深度學習》原文代碼中文注釋版及電子書
圖解word2vec(原文翻譯)
備注:加入本站微信群或者qq群,請回復“加群”
加入知識星球(4100+用戶,ID:92416895),請回復“知識星球”
總結
以上是生活随笔為你收集整理的Python实现递归算法的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 推荐CVer的总结 | 性能最强的目标检
- 下一篇: Python实现快速排序(非递归实现)