首先所有的遞歸都可以使用循環(huán)來替代
遞歸并不是一種高性能解決問題的方式，但使用遞歸可以使代碼更易于理解與閱讀戚篙，更優(yōu)雅
1.什么是遞歸五鲫？
函數(shù)調(diào)用自身就可以稱為遞歸
遞歸需要 ：基線條件和遞歸條件，尤其是基線條件岔擂，否則自身調(diào)用將陷入無限循環(huán)
def cutDown(i):
print(i)
cutDown(i - 1)
if __name__ == '__main__':
cutDown(10)
#以下是錯(cuò)誤日志（當(dāng)print打印到 -993時(shí) 報(bào)錯(cuò)位喂，棧溢出）
[Previous line repeated 993 more times]
File "E:/python/pythonProject1/遞歸.py", line 2, in cutDown
print(i)
RecursionError: maximum recursion depth exceeded while calling a Python object
上述代碼由于缺少基線條件導(dǎo)致，無限循環(huán)
def cutDown(i):
if i < 0: # 當(dāng)i<0時(shí) 退出遞歸
return
else:
print(i)
cutDown(i - 1)
if __name__ == '__main__':
cutDown(10)
上述代碼中 i<0 return 即為 基線條件 用來終止遞歸循環(huán)
else 即為 遞歸條件 用來表明 何時(shí)進(jìn)行 遞歸調(diào)用
2.棧
數(shù)據(jù)結(jié)構(gòu)中的一種乱灵，特點(diǎn)是有序且后進(jìn)先出（棧頂優(yōu)先）塑崖，例如 彈夾
在計(jì)算機(jī)中使用的棧是調(diào)用棧
一般來講它主要負(fù)責(zé)程序的執(zhí)行 （處理函數(shù)的執(zhí)行，以及記錄函數(shù)中的局部變量痛倚，參數(shù)规婆，中間計(jì)算過程等狀態(tài)），它以棧的形式來管理函數(shù)執(zhí)行蝉稳，每當(dāng)執(zhí)行函數(shù)時(shí)抒蚜，就會(huì)壓入一個(gè)棧幀（記錄并執(zhí)行函數(shù)），函數(shù)執(zhí)行完畢耘戚，就會(huì)執(zhí)行出棧嗡髓，修改棧幀，把壓入的內(nèi)容銷毀
舉例：
def greet(name):
print('hello,' + name + "!")
greet2('maggie')
print("getting ready to say bye收津。饿这。。")
bye()
def greet2(name):
print("how are you")
def bye():
print("ok bye!")
if __name__ == '__main__':
greet('maggie')
其實(shí)print也是一個(gè)函數(shù)撞秋，但這里暫時(shí)忽略它
當(dāng)我們調(diào)用 greet('maggie')长捧，計(jì)算機(jī)就會(huì)首先為函數(shù)調(diào)用分配一塊內(nèi)存
我們使用這些內(nèi)存，變量name 被設(shè)置為ning 這需要存儲(chǔ)在內(nèi)存中
*每個(gè)函數(shù)調(diào)用時(shí)部服，計(jì)算機(jī)就會(huì)分配內(nèi)存將唆姐，以棧的形式，將函數(shù)壓入棧中廓八，將調(diào)函數(shù)涉及的所有變量的值存儲(chǔ)在內(nèi)存中奉芦。
接下來 打印hello，maggie剧蹂！ 在調(diào)用greet2（'maggie'）,同樣 greet2（'maggie'） 被分配內(nèi)存壓入棧中声功。
*棧的優(yōu)先級(jí)為后進(jìn)先出，因此棧頂?shù)腉reet2（）將會(huì)執(zhí)行宠叼， 棧底的greet（）將停止執(zhí)行并等待先巴。
接著執(zhí)行Greet2（ ） 打印 how are you , maggie?
Gree2() 執(zhí)行完畢 棧頂?shù)腉reet2（）執(zhí)行出棧，釋放內(nèi)存冒冬，并返回 greet（）
此時(shí)伸蚯，greet（）處于棧頂，由等待轉(zhuǎn)換為繼續(xù)執(zhí)行 简烤，打印getting ready to say bye剂邮。。横侦。
接著執(zhí)行bye()方法 挥萌， bye（）被壓入棧頂，greet()暫停執(zhí)行
執(zhí)行bye（）打印 ok bye! 枉侧，bye （）執(zhí)行完畢引瀑，進(jìn)行出棧，釋放內(nèi)存榨馁，并返回 greet（）
greet() 接著執(zhí)行完畢，greet() 進(jìn)行出棧翼虫，釋放內(nèi)存
這個(gè)存儲(chǔ)多個(gè)函數(shù)數(shù)據(jù)屑柔，狀態(tài)的棧被稱為 調(diào)用棧，調(diào)用棧遵循棧頂優(yōu)先原則
3.遞歸調(diào)用棧
遞歸函數(shù)也是用調(diào)用棧蛙讥！ 我們來分析下階乘算法 n!(5! =54321)
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n - 1)
接下來 我們來分析 factorial(3)的執(zhí)行
當(dāng)執(zhí)行 factorial(3) 時(shí)锯蛀， 將fac（3）壓入棧， 3次慢！=1 所以執(zhí)行 else:
執(zhí)行
這里進(jìn)行遞歸 再次調(diào)用 fac() 函數(shù)旁涤，只不過參數(shù)為2 即 fac(2)
fac(2) 壓入棧頂執(zhí)行，fac(3) 暫停迫像， 2劈愚！=1 所以執(zhí)行 else
進(jìn)行遞歸調(diào)用 fac（2-1）即fac（1）
fac(1) 壓入棧頂執(zhí)行，fac(2) 暫停闻妓，1==1 所以執(zhí)行return 1
fac(1)執(zhí)行完畢 菌羽，出棧，并返回值1
返回fac（2） 繼續(xù)執(zhí)行中斷位置 即為
由缆，執(zhí)行reutn 2
fac(2) 執(zhí)行完畢注祖，出棧猾蒂，并返回值2
返回fac(3)，繼續(xù)執(zhí)行 即
是晨，執(zhí)行return 6
fac(3)執(zhí)行完畢肚菠，出棧，并返回值 6
*每個(gè)fac()調(diào)用都有自己x變量罩缴，在一個(gè)函數(shù)調(diào)用中不能訪問另一個(gè)x的變量
總結(jié)
遞歸是指函數(shù)調(diào)用自己
每個(gè)遞歸函數(shù)都要有兩個(gè)條件：基線條件蚊逢，遞歸條件
棧有兩種操作：壓入和彈出
所以函數(shù)都進(jìn)入調(diào)用
調(diào)用棧可能很長(zhǎng)箫章，這將占用大量?jī)?nèi)存
