python中如何實現遞歸方法

小編給大家分享一下python中如何實現遞歸方法，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

1.遞歸概念

遞歸是解決問題的一種方法，它將問題不斷地分成更小的子問題，直到子問題可以用普通的方法解決。通常情況下，遞歸會使用一個不停調用自己的函數。盡管表面上看起來很普通，但是遞歸可以幫助我們寫出非常優雅的解決方案。對于某些問題，如果不用遞歸，就很難解決。
上面的話很難理解，我們用一個例子來說明：我們需要求解一個數組的所有數值之和。

#用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中如何實現遞歸方法”有了一定的了解，如果想了解更多相關知識，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！