遞歸函數(shù)

什么是遞歸函數(shù)

如果一個函數(shù)，可以自己調(diào)用自己，那么這個函數(shù)就是一個遞歸函數(shù)。

六枝網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)！從網(wǎng)頁設(shè)計、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、響應(yīng)式網(wǎng)站開發(fā)等網(wǎng)站項目制作，到程序開發(fā)，運營維護(hù)。創(chuàng)新互聯(lián)自2013年創(chuàng)立以來到現(xiàn)在10年的時間，我們擁有了豐富的建站經(jīng)驗和運維經(jīng)驗，來保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)。

遞歸，遞就是去，歸就是回，遞歸就是一去一回的過程。

遞歸函數(shù)的條件

一般來說，遞歸需要邊界條件，整個遞歸的結(jié)構(gòu)中要有遞歸前進(jìn)段和遞歸返回段。當(dāng)邊界條件不滿足，遞歸前進(jìn)，反之遞歸返回。就是說遞歸函數(shù)一定需要有邊界條件來控制遞歸函數(shù)的前進(jìn)和返回。

定義一個簡單的遞歸函數(shù)

# 定義一個函數(shù)
def recursion(num):
	
    print(num)
	if num == 0:
		return 'ok'
	
    # 這個函數(shù)在自己的作用域中調(diào)用自己，這個函數(shù)就是一個遞歸函數(shù)
	recursion(num-1)


recursion(10)
"""
結(jié)果：
10
9
8
7
6
5
4
3
2
1
0
"""

代碼解析

我們執(zhí)行這個函數(shù)，參數(shù)給了一個10，但是這個函數(shù)執(zhí)行的過程中，又調(diào)用了自己，所以現(xiàn)在這個函數(shù)就會進(jìn)入先執(zhí)行第二次調(diào)用自己的過程中，第一次的調(diào)用就暫時的阻斷了；

第二次調(diào)用的時候，num-1，參數(shù)就變成了9，繼續(xù)執(zhí)行，然后就又執(zhí)行到了調(diào)用自己的代碼中，現(xiàn)在就會執(zhí)行第三次調(diào)用的過程中，第二次的調(diào)用也阻斷了；

這就是 遞 的過程；

…………

第十一次調(diào)用的時候，num-1，層層的嵌套，參數(shù)就變成了0，就符合了作用域中的if num == 0的條件判斷式，第十一次的調(diào)用就沒有再執(zhí)行到了調(diào)用自己的代碼，而是徹徹底底的執(zhí)行完成了 ，然后代碼的執(zhí)行就又回到了第十次的函數(shù)調(diào)用中。

第十次的函數(shù)調(diào)用阻斷的時候是執(zhí)行到了recursion(num-1)，但是這一行代碼執(zhí)行完了，也就是第十一次調(diào)用執(zhí)行完了，并且后面也沒有任何代碼，所以第十次調(diào)用也結(jié)束了，然后就回到了第九次調(diào)用；然后第八次；再就是第七次，一直到第一次結(jié)束，整個函數(shù)的執(zhí)行就結(jié)束了；

這就是 歸 的過程。

內(nèi)存棧區(qū)堆區(qū)

棧區(qū)空間就是我們常說的棧，棧是一個有去有回，先進(jìn)后出后出的空間，就像我們上面的例子中講的，我們最先執(zhí)行的是函數(shù)的第一次調(diào)用，但是第一次調(diào)用卻是最后執(zhí)行釋放掉的，而第十一次調(diào)用是最后調(diào)用，最先執(zhí)行釋放掉的，這就是先進(jìn)后出。與?？臻g概念相違背的是隊列空間，隊列空間是一個有去有回，先進(jìn)先出的空間，就像我們平時排隊一樣，先排隊的會比后來的人先買到票，之后我們學(xué)習(xí)并發(fā)的時候，我們會詳細(xì)的講述隊列的概念。

單獨的講棧堆就是一種數(shù)據(jù)結(jié)構(gòu)，棧是先進(jìn)后出的一種數(shù)據(jù)結(jié)構(gòu)，堆是排序后的一種樹狀數(shù)據(jù)結(jié)構(gòu)。

棧區(qū)堆區(qū)是內(nèi)存空間，棧區(qū)就是按照先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，無論創(chuàng)建或銷毀都是自動為數(shù)據(jù)分配內(nèi)存，釋放內(nèi)存，這是系統(tǒng)自動創(chuàng)建的；堆區(qū)就是按照排序后的樹狀數(shù)據(jù)結(jié)構(gòu)，可優(yōu)先取出必要的數(shù)據(jù)，無論創(chuàng)建或者銷毀都是手動分配內(nèi)存，釋放內(nèi)存，這是編程工作者手動編程出來的。

內(nèi)存空間	特點
內(nèi)存中的棧區(qū)	自動分配，自動釋放
內(nèi)存中的堆區(qū)	手動分配，手動釋放

運行程序時在內(nèi)存中執(zhí)行，會因為數(shù)據(jù)類型的不同而在內(nèi)存的不同區(qū)域運行，因不同語言對內(nèi)存劃分的機(jī)制不一，當(dāng)大體來說，有如下四大區(qū)域：

1. 棧區(qū)：分配局部變量空間；
2. 堆區(qū)：是用于手動分配程序員申請的內(nèi)存空間；
3. 靜態(tài)區(qū)：又稱之為全局棧區(qū)，分配靜態(tài)變量，全局變量空間；
4. 代碼區(qū)：又稱之為只讀區(qū)、常量區(qū)，分配常量和程序代碼空間；

上面的棧區(qū)、讀取、靜態(tài)區(qū)、代碼區(qū)都只是內(nèi)存中的一段空間。

死遞歸

所以我們在使用遞歸函數(shù)的時候要注意，遞歸函數(shù)調(diào)用的過程就是一個開辟棧和釋放棧的過程，調(diào)用的時候開辟?？臻g，結(jié)束的時候釋放棧空間，所以說，如果開辟的空間不結(jié)束就會一直存在，就會一直占用內(nèi)存空間，但是?？臻g是一個先進(jìn)后出的空間，如果新開啟的空間不釋放掉，之前的空間也不會釋放掉的，那么如果我們開辟的空間很多很多，但是又釋放不掉，那么我們?nèi)跣〉膬?nèi)存是否有足夠的空間容納得下這么多的棧呢？如果容納不下，那么我們的計算機(jī)就會爆炸，所以我們在使用遞歸的時候要注意避免這種情況。尤其是死遞歸。

每次調(diào)用函數(shù)時，在內(nèi)存宗都會單獨開辟一個空間，配合函數(shù)運行，這個空間叫做棧幀空間。

1、遞歸是一去一回的過程，調(diào)用函數(shù)時，會開辟棧幀空間，函數(shù)執(zhí)行結(jié)束之后，會釋放棧幀空間，遞歸實際上就是不停地開辟和釋放棧幀空間的過程，每次開辟棧幀空間，都是獨立的一份，其中的資源不共享。

2、觸發(fā)回的過程當(dāng)最后一層棧幀空間全部執(zhí)行結(jié)束的時候，會觸底反彈，回到上一層空間的調(diào)用處，遇到return，會觸底反彈，回到上一層的調(diào)用處

3、寫遞歸時，必須給予遞歸跳出的條件，否則會發(fā)生內(nèi)存溢出，可能會出現(xiàn)死機(jī)的情況，所以當(dāng)遞歸的層數(shù)過多的時候，不建議使用遞歸。

Python中的環(huán)境遞歸的層數(shù)默認(rèn)為1000層左右，一般都是996層。

# 下面的遞歸函數(shù)沒有跳出遞歸的條件，所以是一個死遞歸，執(zhí)行看，是不是1000左右。
def recursion(num):
	print(num)
	recursion(num+1)

recursion(1)

尾遞歸

簡單的來說，在函數(shù)返回的時候，調(diào)用其本身，并且return語句不包含表達(dá)式，這樣的一個遞歸函數(shù)就是一個尾遞歸函數(shù)。

換句話說返回的東西就是函數(shù)本身就是尾遞歸函數(shù)，而遞歸函數(shù)只是自身調(diào)用了自身而已。

一般情況下，尾遞歸的計算在參數(shù)中完成。

我們開始的舉例是一個尾遞歸函數(shù)嗎？不是，因為那個例子這是調(diào)用了自己本省，但是并沒有返回，所以還是一個普通的遞歸函數(shù)而已。

使用遞歸的時候，我們通常在一些技術(shù)博客上看到一些關(guān)于尾遞歸優(yōu)化的東西，這是因為尾遞歸無論調(diào)用多少次函數(shù)，都只會占用一份空間，只開辟一個棧幀空間，但是目前 cpython 不支持，然而最常見的解釋器就是 cpython 。

Python常見的解釋器：cpython、pypy、jpython。

尾遞歸相比普通遞歸的優(yōu)點就是返回值不需要額外過多的運算。

實例

階乘計算

一個正整數(shù)的階乘是所有小于及等于該數(shù)的正整數(shù)的積，并且0的階乘為1。

""" 循環(huán)計算 """
def factorial(num):
   if num == 0:
      return 1
   elif num < -1:
      return '只能是零和正整數(shù)'
   count = 1
   for i in range(1, num+1):
      count *= i
   return count

res = factorial(5)
print(res)  # 120


""" 使用普通遞歸 """
def factorial(num):
   if num == 0:
      return 1
   elif num < -1:
      return '只能是零和正整數(shù)'
   elif num == 1:
      return num
   return num * factorial(num-1)   # 普通函數(shù)返回的是一個表達(dá)式

res = factorial(5)
print(res)  # 120


""" 使用尾遞歸 """
def factorial(num, count=1):
   if num == 0:
      return 1
   elif num < -1:
      return '只能是零和正整數(shù)'
   elif num == 1:
      return count
   return factorial(num-1, count*num)   # 尾遞歸返回的是一個函數(shù)，計算式在參數(shù)中運算

res = factorial(5)
print(res)  # 120

斐波那契數(shù)列

斐波那契數(shù)列是以0、1兩個數(shù)開頭，從這個數(shù)列從第3個數(shù)開始，每一個數(shù)都等于前兩樹之和。

# 使用循環(huán)解決
def fibonacci(num):
   x, y = 0, 1

   if num < 1:
      return '輸入大于0的數(shù)字'
   elif num == 1:
      return 0
   elif num == 2:
      return 1

   for _ in range(num-2):
      x, y = y, y+x
   return y

res = fibonacci(9)
print(res)  # 21


""" 使用普通遞歸 """
def fibonacci(num):
   if num < 1:
      return '輸入大于0的數(shù)字'
   elif num == 1:
      return 0
   elif num == 2:
      return 1

   return fibonacci(num-1) + fibonacci(num-2)

res = fibonacci(9)
print(res)  # 21


""" 使用尾遞歸 """
def fibonacci(num, x=0, y=1):
   if num < 1:
      return '輸入大于0的數(shù)字'
   elif num == 1:
      return x
   elif num == 2:
      return y

   return fibonacci(num-1, x=y,  y=(x+y))

res = fibonacci(9)
print(res)  # 21

網(wǎng)站欄目：Python 函數(shù)進(jìn)階-遞歸函數(shù)
本文路徑：http://m.kartarina.com/article32/dsogpsc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站設(shè)計、營銷型網(wǎng)站建設(shè)、微信公眾號、網(wǎng)頁設(shè)計公司、網(wǎng)站改版、用戶體驗

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)