遞迴確實是一種較為抽象的數學邏輯,可以簡單的理解為「程式呼叫自身的演算法」。
維基百科對遞歸的解釋是:
遞歸(英語: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))
使用數學方法進行推導:
其實以上兩個遞歸的案例都可以用數學歸納法來解釋,就是高中數學學的知識。
一般地,證明一個與自然數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)
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中文網其他相關文章!