今天小編給大家分享一下Python遞歸算法是什么的相關(guān)知識(shí)點(diǎn)，內(nèi)容詳細(xì)，邏輯清晰，相信大部分人都還太了解這方面的知識(shí)，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來(lái)了解一下吧。

10年積累的成都網(wǎng)站設(shè)計(jì)、網(wǎng)站制作經(jīng)驗(yàn)，可以快速應(yīng)對(duì)客戶對(duì)網(wǎng)站的新想法和需求。提供各種問(wèn)題對(duì)應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先網(wǎng)站設(shè)計(jì)制作后付款的網(wǎng)站建設(shè)流程，更有鼓樓免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

遞歸確實(shí)是一種較為抽象的數(shù)學(xué)邏輯，可以簡(jiǎn)單的理解為「程序調(diào)用自身的算法」。

維基百科對(duì)遞歸的解釋是：

遞歸(英語(yǔ)：Recursion)，又譯為遞回，在數(shù)學(xué)與計(jì)算機(jī)科學(xué)中，是指在函數(shù)的定義中使用函數(shù)自身的方法。遞歸一詞還較常用于描述以自相似方法重復(fù)事物的過(guò)程。

例如，當(dāng)兩面鏡子相互之間近似平行時(shí)，鏡中嵌套的圖像是以無(wú)限遞歸的形式出現(xiàn)的。也可以理解為自我復(fù)制的過(guò)程。

"遞"是傳遞的意思，"歸"是歸還的意思，先把一個(gè)方法一層層傳遞下去，然后傳遞到最后一層再把結(jié)果歸還回來(lái)。

比方說(shuō)我排隊(duì)做核酸檢測(cè)，前面有100個(gè)人，我想問(wèn)下醫(yī)務(wù)人員幾點(diǎn)下班，于是問(wèn)了我前面那兄弟，他又問(wèn)了他前面的人，一個(gè)個(gè)傳遞下去，最終傳遞到了醫(yī)務(wù)人員那里，回話說(shuō)下午六點(diǎn)下班。這句話又往回傳，最終到了我這里，我知道了醫(yī)務(wù)人員六點(diǎn)下班。

這個(gè)過(guò)程就是一個(gè)遞歸過(guò)程，如果說(shuō)"傳話"本身是一種方法，那這整個(gè)傳話過(guò)程就是在調(diào)用自身方法，最終獲得了結(jié)果。

這和循環(huán)不一樣，循環(huán)相當(dāng)于給所有人都所有人都戴了耳機(jī)，然后有"中介"挨個(gè)去問(wèn)你知道醫(yī)務(wù)人員幾點(diǎn)下班嗎，等問(wèn)到醫(yī)務(wù)人員的時(shí)候，得到答案，“中介”告訴我六點(diǎn)下班。

實(shí)質(zhì)上，遞歸就是把一個(gè)大問(wèn)題不斷拆解，像剝洋蔥一樣，最終拆解到最小層面，會(huì)返回解題結(jié)果。

用Python舉一個(gè)最簡(jiǎn)單的遞歸函數(shù)例子，講一講什么是遞歸的應(yīng)用。

我們經(jīng)常會(huì)看到函數(shù)會(huì)調(diào)用自身來(lái)實(shí)現(xiàn)循環(huán)操作，比如求階乘的函數(shù)。

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

如下面5行Python代碼，就能實(shí)現(xiàn)階乘的計(jì)算。

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

很多人可能困惑這里面的計(jì)算邏輯，為什么fact函數(shù)中調(diào)用了自身，最終能得到結(jié)果。

我們可以按照數(shù)學(xué)邏輯進(jìn)行推演：

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

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

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

這里是不是一種 fact方法可以為每個(gè)數(shù)所調(diào)用，最終調(diào)用到了n=1的時(shí)候，就返回結(jié)果n的階乘。

大家看上圖，遞歸函數(shù)會(huì)一層層往下調(diào)用，最終到n=1的時(shí)候，往上返回結(jié)果。

這就是遞歸的全過(guò)程，如果我們給遞歸下一個(gè)準(zhǔn)確的定義，可以概括為以下3點(diǎn)：

1、至少有一個(gè)明確的遞歸結(jié)束條件。

2、給出遞歸終止時(shí)的處理辦法。

3、每次進(jìn)入更深一層遞歸時(shí)，問(wèn)題規(guī)模(計(jì)算量)相比上次遞歸都應(yīng)有所減少。

以上面代碼為例：

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

除了常見(jiàn)的階乘案例，還有斐波那契數(shù)列，也是遞歸的經(jīng)典用法。

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

這個(gè)數(shù)列從第3項(xiàng)開(kāi)始，每一項(xiàng)都等于前兩項(xiàng)之和。

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

在Python中，我們可以使用遞歸函數(shù)的方式去實(shí)現(xiàn)斐波那契數(shù)列：

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

print(fab(12))

使用數(shù)學(xué)方法進(jìn)行推導(dǎo)：

• fab(0) = 0(初始值)。

• fab(1) = 1(初始值)。

• 對(duì)所有大于1的整數(shù)n：fab(n) = fab(n-1)+ fab(n-2)(遞歸定義)。

其實(shí)以上兩個(gè)遞歸的案例都可以用數(shù)學(xué)歸納法來(lái)解釋，就是高中數(shù)學(xué)學(xué)的知識(shí)。

一般地，證明一個(gè)與自然數(shù)n有關(guān)的命題P(n)，有如下步驟：

(1)證明當(dāng)n取第一個(gè)值n0時(shí)命題成立。n0對(duì)于一般數(shù)列取值為0或1，但也有特殊情況。

(2)假設(shè)當(dāng)n=k(k≥n0，k為自然數(shù))時(shí)命題成立，證明當(dāng)n=k+1時(shí)命題也成立。

綜合(1)(2)，對(duì)一切自然數(shù)n(≥n0)，命題P(n)都成立。

除了數(shù)學(xué)的解釋，之前也看到有人對(duì)遞歸更加形象的解釋：

1、我們已經(jīng)完成了嗎?如果完成了，返回結(jié)果。如果沒(méi)有這樣的終止條件，遞歸將會(huì)永遠(yuǎn)地繼續(xù)下去。

2、如果沒(méi)有，則簡(jiǎn)化問(wèn)題，解決較容易的問(wèn)題，并將結(jié)果組裝成原始問(wèn)題的解決辦法。然后返回該解決辦法。

哈哈,到這里大家是不是對(duì)遞歸有了一個(gè)更加深刻的認(rèn)識(shí)。

如果還不清楚，沒(méi)關(guān)系，這里還有更多的遞歸案例，用Python來(lái)實(shí)現(xiàn)，可以說(shuō)非常簡(jiǎn)潔。

「最大公因數(shù)：」

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

「從 1 到 n 的數(shù)字之和：」

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))

「漢諾塔問(wèn)題：」

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('向左側(cè)找！')
return dichotomy(min,mid,d,n)
else:
print('找到了%s'%d[mid])
return 
res = dichotomy(0,len(data),data,222)
print(res)

有位大佬說(shuō)過(guò)：To Iterate is Human, to Recurse, Divine。

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

可見(jiàn)遞歸是非常神奇的算法，它的神奇之處在于它允許用戶用有限的語(yǔ)句描述無(wú)限的對(duì)象。

當(dāng)然人無(wú)完人，遞歸也是有缺點(diǎn)的，它一般效率較低，且會(huì)導(dǎo)致調(diào)用棧溢出。

因?yàn)檫f歸不斷調(diào)用自身函數(shù)，且產(chǎn)生大量變量，而棧空間的容量是有限的，循環(huán)太多就會(huì)效率低下，甚至導(dǎo)致調(diào)用棧溢出。

以上就是“Python遞歸算法是什么”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會(huì)為大家更新不同的知識(shí)，如果還想學(xué)習(xí)更多的知識(shí)，請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。