python數據結構之遞歸方法講解
今天我們來學習python中最為重要的內容之遞歸,對以往內容感興趣的同學可以查看下面:
python數據類型: python數據結構:數據類型.
python的輸入輸出: python數據結構之輸入輸出、控制和異常.
python面向對象: python數據結構之面向對象.
python算法分析: python數據結構算法分析.
python數據結構之棧、隊列和雙端隊列
遞歸是在進行重復性工作中經常考到的問題,非常值得學習。
遞歸是解決問題的一種方法,它將問題不斷地分成更小的子問題,直到子問題可以用普通的方法解決。通常情況下,遞歸會使用一個不停調用自己的函數。盡管表面上看起來很普通,但是遞歸可以幫助我們寫出非常優雅的解決方案。對於某些問題,如果不用遞歸,就很難解決。
上面的話很難理解,我們用一個例子來說明:我們需要求解一個數組的所有數值之和。
#用for循環的簡單函數 def getsum(numlist): a=0 for i in numlist: a=i+a return a
結果如下:
如果暫時沒有 while
循環和 for 循環。應該如何計算結果呢? 這個時候就需要想到我們計算加法的時候,是接受2個參數的函數,根據這個思想,我們將求一列數之和重新定義成求數字對之和。
註:最內層的括號對(7 + 9)不用 循環或者其他特殊語法結構就能直接求解。
擬代碼表示
#first(list)返回列表中的第一個元素,rest(list)則返回其餘元素。用 Python 可以輕松地實現這個等式, getsum(list)=first(list)+getsum(rest(list))
代碼表示:
#這是一個遞歸小案例,這個函數在函數內部自己調用瞭自listsum(numlist[1:]) def listsum(numlist): if len(numlist)==1:#當數組的長度為1時,代表是數組是一個數瞭 return numlist[0] else: return numlist[0] + listsum(numlist[1:])#第一個數加上後面的數,這裡自己調用瞭自己,是數組不斷遞歸的條件
在這一段代碼中,有兩個重要的思想值得探討。首先,第 2 行檢查列表是否隻包含一個元素。 這個檢查非常重要,同時也是該函數的退出語句。對於長度為 1 的列表,其元素之和就是列表中的數。其次,listsum 函數在第 5 行調用瞭自己!這就是我們將 listsum
稱為遞歸函數的原因——遞歸函數會調用自己。
演示一下相加過程
2. 遞歸三原則
遞歸算法有三個重要的原則:
- 遞歸算法必須有停止條件
- 遞歸算法必須改變其狀態並向停止條件靠近
- 遞歸算法必須遞歸地調用自己
讓我們看看我們第一個案例是怎麼實現這個部分的:
len(numlist)==1
用來判斷停止條件numlist[1:]
代表問題的數據以某種方式變得更小return numlist[0] + listsum(numlist[1:])
代表遞歸地調用自己
遞歸的邏輯並不是循環,而是將問題分解成更小、更容易解決的子問題。
2.1 實現任意進制的數據轉換
下面展示一下將10進制的29轉換為2進制數的方法,按照這個方法,可以將10進制轉化為任意進制的數。
這裡我們用遞歸來實現2~16進制數的轉換
#n代表要轉化的10進制數,base代表你要實現的多少進制的數 def toStr(n, base): convertString = "0123456789ABCDEF"#取對應位置的字符 if n < base:#如果10進制數小於你所轉換的進制數位數,則直接選擇字符 return convertString[n] else:#遞歸核心,n//base獲取結果,然後進行遞歸 return toStr(n//base, base) + convertString[n%base]
將15轉化為16進制數
將15轉化為2進制數
到此這篇關於python數據結構之遞歸方法講解的文章就介紹到這瞭,更多相關python遞歸內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!