Python中遞歸算法怎么用

小編給大家分享一下Python中遞歸算法怎么用，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

遞歸是一種較為抽象的數學邏輯，可以簡單的理解為「程序調用自身的算法」。

維基百科對遞歸的解釋是：

遞歸（英語：Recursion），又譯為遞回，在數學與計算機科學中，是指在函數的定義中使用函數自身的方法。遞歸一詞還較常用于描述以自相似方法重復事物的過程。

例如，當兩面鏡子相互之間近似平行時，鏡中嵌套的圖像是以無限遞歸的形式出現的。也可以理解為自我復制的過程。

"遞"是傳遞的意思，"歸"是歸還的意思，先把一個方法一層層傳遞下去，然后傳遞到最后一層再把結果歸還回來。

比方說我排隊做核酸檢測，前面有100個人，我想問下醫務人員幾點下班，于是問了我前面那兄弟，他又問了他前面的人，一個個傳遞下去，最終傳遞到了醫務人員那里，回話說下午六點下班。這句話又往回傳，最終到了我這里，我知道了醫務人員六點下班。

這個過程就是一個遞歸過程，如果說"傳話"本身是一種方法，那這整個傳話過程就是在調用自身方法，最終獲得了結果。

這和循環不一樣，循環相當于給所有人都所有人都戴了耳機，然后有"中介"挨個去問你知道醫務人員幾點下班嗎，等問到醫務人員的時候，得到答案，“中介”告訴我六點下班。

實質上，遞歸就是把一個大問題不斷拆解，像剝洋蔥一樣，最終拆解到最小層面，會返回解題結果。

用Python舉一個最簡單的遞歸函數例子，講一講什么是遞歸的應用。

我們經常會看到函數會調用自身來實現循環操作，比如求階乘的函數。

整數n的階乘即n*(n-1)*(n-2)*...*3*2*1

如下面5行Python代碼，就能實現階乘的計算

def fact(n):
    ''' n表示要求的數的階乘 '''
    if n==1:
        return n 
    n = n*fact(n-1)
    return n  

print(factorial(5))

輸出：

120

很多人可能困惑這里面的計算邏輯，為什么fact函數中調用了自身，最終能得到結果。

我們可以按照數學邏輯進行推演：

整數n的階乘是：fact(n) = n*(n-1)*...*3*2*1

整數n-1的階乘是：fact(n-1) = (n-1)*(n-2)*...*3*2*1

所以可以推斷 fact(n) = n*fact(n-1)

這里是不是一種 fact方法可以為每個數所調用，最終調用到了n=1的時候，就返回結果n的階乘。

大家看上圖，遞歸函數會一層層往下調用，最終到n=1的時候，往上返回結果。

這就是遞歸的全過程，如果我們給遞歸下一個準確的定義，可以概括為以下3點：

1、至少有一個明確的遞歸結束條件；

2、給出遞歸終止時的處理辦法；

3、每次進入更深一層遞歸時，問題規模(計算量)相比上次遞歸都應有所減少

以上面代碼為例：

def factorial(n):
    ''' n表示要求的數的階乘 '''
    if n==1: # 1、明確遞歸終止條件；
        return n # 2、遞歸終止時的處理辦法
    n = n*factorial(n-1) # 遞去
    return n  # 歸來

除了常見的階乘案例，還有斐波那契數列，也是遞歸的經典用法。

斐波那契數列：1，1，2，3，5，8，13，21，34，55，89...

這個數列從第3項開始，每一項都等于前兩項之和。

它以如下被以遞推的方法定義：F(0)=0，F(1)=1,F(n)=F(n - 1)+F(n - 2)（n≥ 2，n∈ N*）

在Python中，我們可以使用遞歸函數的方式去實現斐波那契數列：

# 1，1，2，3，5，8，13，21，34，55，試判斷數列第12個數是哪個？
def fab(n):
    ''' n為斐波那契數列 '''
    if n <= 2:
        v = 1
        return v 
    v = fab(n-1)+fab(n-2) 
    return v  

print(fab(12))

使用數學方法進行推導：

• fab(0) = 0（初始值）

• fab(1) = 1（初始值）

• 對所有大于1的整數n：fab(n) = fab(n-1)+ fab(n-2)（遞歸定義）

其實以上兩個遞歸的案例都可以用數學歸納法來解釋，就是高中數學的知識。

一般地，證明一個與自然數n有關的命題P(n），有如下步驟：

（1）證明當n取第一個值n0時命題成立。n0對于一般數列取值為0或1，但也有特殊情況；

（2）假設當n=k（k≥n0，k為自然數）時命題成立，證明當n=k+1時命題也成立。

綜合（1）（2），對一切自然數n（≥n0），命題P(n）都成立。

除了數學的解釋，之前也看到有人對遞歸更加形象的解釋：

1、我們已經完成了嗎？如果完成了，返回結果。如果沒有這樣的終止條件，遞歸將會永遠地繼續下去。

2、如果沒有，則簡化問題，解決較容易的問題，并將結果組裝成原始問題的解決辦法。然后返回該解決辦法。

哈哈,到這里大家是不是對遞歸有了一個更加深刻的認識。

如果還不清楚，沒關系，這里還有更多的遞歸案例，用Python來實現，可以說非常簡潔。

「最大公因數：」

def gcd(m, n):
    if n == 0:
        return m
    else:
        return gcd(n, m%n)

「從 1 到 n 的數字之和：」

def sumnums(n):
    if n == 1:
        return 1
    return n + sumnums(n - 1)

print(sumnums(3))

「字符串倒序：」

def reverse(string):
    if len(string) == 0:
        return string
    else:
        return reverse(string[1:]) + string[0]

reverseme = '我是帥哥'
print(reverse(reverseme))

「漢諾塔問題：」

def towerOfHanoi(numrings, from_pole, to_pole, aux_pole):
    if numrings == 1:
        print('Move ring 1 from', from_pole, 'pole to', to_pole, 'pole')
        return
    towerOfHanoi(numrings - 1, from_pole, aux_pole, to_pole)
    print('Move ring', numrings, 'from', from_pole, 'pole to', to_pole, 'pole')
    towerOfHanoi(numrings - 1, aux_pole, to_pole, from_pole)


numrings = 2
towerOfHanoi(numrings, 'Left', 'Right', 'Middle')

「二分法找有序列表指定值：」

data = [1,3,6,13,56,123,345,1024,3223,6688]
def dichotomy(min,max,d,n):
    '''
    min表示有序列表頭部索引
    max表示有序列表尾部索引
    d表示有序列表
    n表示需要尋找的元素
    '''
    mid = (min+max)//2
    if mid==0:
        return 'None'
    elif d[mid]<n:
        print('向右側找！')
        return dichotomy(mid,max,d,n)
    elif d[mid]>n:
        print('向左側找！')
        return dichotomy(min,mid,d,n)
    else:
        print('找到了%s'%d[mid])
        return 
res = dichotomy(0,len(data),data,222)
print(res)

有位大佬說過：To Iterate is Human, to Recurse, Divine.

中文譯為：人理解迭代，神理解遞歸。

可見遞歸是非常神奇的算法，它的神奇之處在于它允許用戶用有限的語句描述無限的對象。

當然人無完人，遞歸也是有缺點的，它一般效率較低，且會導致調用棧溢出。

因為遞歸不斷調用自身函數，且產生大量變量，而棧空間的容量是有限的，循環太多就會效率低下，甚至導致調用棧溢出

以上是“Python中遞歸算法怎么用”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！