如何更好地理解遞歸演算法？ 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))

很多人可能困惑這裡面的計算邏輯，為什麼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實例詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！