今天我們來學(xué)習(xí)python中最為重要的內(nèi)容之遞歸，對以往內(nèi)容感興趣的同學(xué)可以查看下面：

python數(shù)據(jù)類型: python數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)類型.
python的輸入輸出: python數(shù)據(jù)結(jié)構(gòu)之輸入輸出、控制和異常.
python面向?qū)ο? python數(shù)據(jù)結(jié)構(gòu)之面向?qū)ο?
python算法分析: python數(shù)據(jù)結(jié)構(gòu)算法分析.
python數(shù)據(jù)結(jié)構(gòu)之棧、隊(duì)列和雙端隊(duì)列

遞歸是在進(jìn)行重復(fù)性工作中經(jīng)?？嫉降膯栴}，非常值得學(xué)習(xí)。

1.遞歸概念

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

#用for循環(huán)的簡單函數(shù)
def getsum(numlist):
    a=0
    for i in numlist:
        a=i+a
    return a

結(jié)果如下：

如果暫時(shí)沒有 while 循環(huán)和 for 循環(huán)。應(yīng)該如何計(jì)算結(jié)果呢? 這個(gè)時(shí)候就需要想到我們計(jì)算加法的時(shí)候，是接受2個(gè)參數(shù)的函數(shù)，根據(jù)這個(gè)思想，我們將求一列數(shù)之和重新定義成求數(shù)字對之和。

注：最內(nèi)層的括號(hào)對(7 + 9)不用 循環(huán)或者其他特殊語法結(jié)構(gòu)就能直接求解。
擬代碼表示

#first(list)返回列表中的第一個(gè)元素，rest(list)則返回其余元素。用 Python 可以輕松地實(shí)現(xiàn)這個(gè)等式，
getsum(list)=first(list)+getsum(rest(list))

代碼表示：

#這是一個(gè)遞歸小案例，這個(gè)函數(shù)在函數(shù)內(nèi)部自己調(diào)用了自listsum(numlist[1:])
def listsum(numlist):
    if len(numlist)==1:#當(dāng)數(shù)組的長度為1時(shí)，代表是數(shù)組是一個(gè)數(shù)了
        return numlist[0]
    else:
        return numlist[0] + listsum(numlist[1:])#第一個(gè)數(shù)加上后面的數(shù)，這里自己調(diào)用了自己，是數(shù)組不斷遞歸的條件

在這一段代碼中，有兩個(gè)重要的思想值得探討。首先，第 2 行檢查列表是否只包含一個(gè)元素。 這個(gè)檢查非常重要，同時(shí)也是該函數(shù)的退出語句。對于長度為 1 的列表，其元素之和就是列表中的數(shù)。其次，listsum 函數(shù)在第 5 行調(diào)用了自己!這就是我們將 listsum 稱為遞歸函數(shù)的原因——遞歸函數(shù)會(huì)調(diào)用自己。

演示一下相加過程

2. 遞歸三原則

遞歸算法有三個(gè)重要的原則：

• 遞歸算法必須有停止條件
• 遞歸算法必須改變其狀態(tài)并向停止條件靠近
• 遞歸算法必須遞歸地調(diào)用自己

讓我們看看我們第一個(gè)案例是怎么實(shí)現(xiàn)這個(gè)部分的：

• len(numlist)==1 用來判斷停止條件
• numlist[1:] 代表問題的數(shù)據(jù)以某種方式變得更小
• return numlist[0] + listsum(numlist[1:]) 代表遞歸地調(diào)用自己

遞歸的邏輯并不是循環(huán)，而是將問題分解成更小、更容易解決的子問題。

2.1 實(shí)現(xiàn)任意進(jìn)制的數(shù)據(jù)轉(zhuǎn)換

下面展示一下將10進(jìn)制的29轉(zhuǎn)換為2進(jìn)制數(shù)的方法，按照這個(gè)方法，可以將10進(jìn)制轉(zhuǎn)化為任意進(jìn)制的數(shù)。

這里我們用遞歸來實(shí)現(xiàn)2~16進(jìn)制數(shù)的轉(zhuǎn)換

#n代表要轉(zhuǎn)化的10進(jìn)制數(shù)，base代表你要實(shí)現(xiàn)的多少進(jìn)制的數(shù)
def toStr(n, base):
    convertString = "0123456789ABCDEF"#取對應(yīng)位置的字符
    if n < base:#如果10進(jìn)制數(shù)小于你所轉(zhuǎn)換的進(jìn)制數(shù)位數(shù)，則直接選擇字符
        return convertString[n]
    else:#遞歸核心，n//base獲取結(jié)果，然后進(jìn)行遞歸
        return toStr(n//base, base) + convertString[n%base]

到此這篇關(guān)于python數(shù)據(jù)結(jié)構(gòu)之遞歸方法講解的文章就介紹到這了,更多相關(guān)python遞歸內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論