如果一個函數(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)。
遞歸，遞就是去，歸就是回，遞歸就是一去一回的過程。
一般來說，遞歸需要邊界條件，整個遞歸的結(jié)構(gòu)中要有遞歸前進(jìn)段和遞歸返回段。當(dāng)邊界條件不滿足，遞歸前進(jìn)，反之遞歸返回。就是說遞歸函數(shù)一定需要有邊界條件來控制遞歸函數(shù)的前進(jìn)和返回。
重慶分公司
重慶分公司
# 定義一個函數(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é)束了；
這就是 歸 的過程。
棧區(qū)空間就是我們常說的棧，棧是一個有去有回，先進(jìn)后出后出的空間，就像我們上面的例子中講的，我們最先執(zhí)行的是函數(shù)的第一次調(diào)用，但是第一次調(diào)用卻是最后執(zhí)行釋放掉的，而第十一次調(diào)用是最后調(diào)用，最先執(zhí)行釋放掉的，這就是先進(jìn)后出。與棧空間概念相違背的是隊列空間，隊列空間是一個有去有回，先進(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ū)域：
上面的棧區(qū)、讀取、靜態(tài)區(qū)、代碼區(qū)都只是內(nèi)存中的一段空間。
所以我們在使用遞歸函數(shù)的時候要注意，遞歸函數(shù)調(diào)用的過程就是一個開辟棧和釋放棧的過程，調(diào)用的時候開辟棧空間，結(jié)束的時候釋放?？臻g，所以說，如果開辟的空間不結(jié)束就會一直存在，就會一直占用內(nèi)存空間，但是棧空間是一個先進(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
