1.介紹
一說起遞歸，我想每個人都不陌生亥揖。舉個從小就聽過的例子：從前有座山党晋，山里有座廟，廟里有個和尚徐块，和尚在講故事未玻，從前有座山，山里有座廟胡控，廟里有個和尚扳剿，和尚在講故事，從前有座山...
還有你從兩面相對的鏡子中看到的畫面昼激，其實都是抽象出來的遞歸現(xiàn)象庇绽，但是嚴(yán)格來說并不是遞歸锡搜，因為會一直重復(fù)下去，沒有終止條件瞧掺，那就稱為死循環(huán)了耕餐。有關(guān)遞歸和死循環(huán)的異同我們之后會說到，那么現(xiàn)在先來了解一下什么是遞歸?
那么什么是遞歸呢辟狈？要理解遞歸肠缔，就的先了解什么是遞歸，實際上這句話就是一個遞歸哼转。這么說可能不好理解明未，接下來舉個簡單的例子來解釋這段話的意義。
假設(shè)我們現(xiàn)在都不知道什么是遞歸壹蔓，我們自然想到打開瀏覽器：輸入到谷歌的網(wǎng)頁趟妥，點擊搜索遞歸，然后在為維基百科中了解到了遞歸的基本定義佣蓉。在了解到了遞歸實際上是和棧有關(guān)的時候披摄，你又蒙圈了，什么是棧呢勇凭？數(shù)據(jù)結(jié)構(gòu)沒學(xué)清楚行疏，此時的你只能又打開谷歌，搜索什么是棧套像。接下來你依次了解了內(nèi)存/操作系統(tǒng)酿联。在你基本了解好知識之后，你通過操作系統(tǒng)了解了內(nèi)存夺巩，通過內(nèi)存了解了棧铐拐，通過棧了解了什么是遞歸這下你恍然大悟谐丢！原來這就是遞歸啊！
假設(shè)我們現(xiàn)在都不知道什么是遞歸尼酿，我們自然想到打開瀏覽器：輸入到谷歌的網(wǎng)頁拆撼，點擊搜索遞歸竞阐，然后在為維基百科中了解到了遞歸的基本定義眠饮。在了解到了遞歸實際上是和棧有關(guān)的時候，你又蒙圈了制跟，什么是棧呢舅桩？數(shù)據(jù)結(jié)構(gòu)沒學(xué)清楚，此時的你只能又打開谷歌雨膨，搜索什么是棧擂涛。接下來你依次了解了內(nèi)存/操作系統(tǒng)。在你基本了解好知識之后聊记，你通過操作系統(tǒng)了解了內(nèi)存撒妈，通過內(nèi)存了解了棧恢暖，通過棧了解了什么是遞歸這下你恍然大悟！原來這就是遞歸罢摇杰捂！
2.示例
也許之前你在網(wǎng)絡(luò)上看到過這張圖片：
實際上這張圖很形象地表達(dá)出了遞歸，這句嚇得我抱起了抱著抱著抱著我的小鯉魚的我的我的我如果從字面義上看可能看不出是什么意思棋蚌，那么我們可以通過代碼來實現(xiàn)同樣的效果：
function Recursion(depth) {
console.log('抱著');
if (!depth) {
console.log('我的小鯉魚')
} else {
Recursion(--depth);// 遞歸調(diào)動
}
console.log('的我')嫁佳；
}
console.log('嚇得我抱起了')；
Recursion（2）
在終端的打印結(jié)果為如下附鸽，可以看到和上面的那段話是一樣的：
嚇得我抱起了
抱著
抱著
抱著
我的小鯉魚
的我
的我
的我
代碼其實十分簡單脱拼，但是需要理解的是:if代碼塊的條件(!depth)為遞歸調(diào)用的終止條件瞒瘸，在else代碼塊內(nèi)遞歸調(diào)用函數(shù).我們前面有說到遞歸的過程是存在前行和退回階段的坷备，那么在前行階段我們在每次調(diào)用函數(shù)后，打印出了"抱著"情臭，并且當(dāng)depth≠0時重新調(diào)用該函數(shù);在退回階段省撑，將會去執(zhí)行代碼console.log('的我');再打印出"的我".
褚躍躍的圖也能比較清楚地反映出這個過程:
好了！這下你應(yīng)該明白什么是遞歸了吧俯在？如果你還沒明白什么是遞歸的話竟秫，你可以看什么是遞歸？
3.應(yīng)用
3.1 斐波拉契數(shù)列
有關(guān)遞歸應(yīng)用的應(yīng)用很多跷乐，例如注明的斐波拉契數(shù)列就可以通過遞歸來實現(xiàn)：
def fib(x) :
if x < 2:
return 0 if x == 0 else 1
//當(dāng) x > 2時肥败， 開始遞歸調(diào)用 fib（）函數(shù)：
return fib（x - 1） + fib （x - 2）
print（fib（6））//打印結(jié)果為：8
這里需要對i<2時的特殊情況做出判斷，當(dāng)x==0時愕提，直接返回0馒稍，當(dāng)x==1時，直接返回1
3.2遍歷文件
首先我們需要了解遍歷的算法：定義的file_display函數(shù)以某個目錄(/home/pushy)作為遍歷的起點.遇到一個子目錄時浅侨，就先接著遍歷子目錄(遞歸調(diào)用函數(shù))纽谒。遇到一個文件時，就直接對改文件進(jìn)行操作(這里只打印出文件的文件名):
import os
def file_display(filepath):
for each in os.listdir(filepath):
# 得到文件的絕對路徑:
absolute_path = os.path.join(filepath如输， each)
# 得到是否為文件還是目錄的布爾值:
is_file = os.path.isfile(absolute_path)
if is_file:
# 當(dāng)前的絕對路徑為文件:
print(each)
else:
# 當(dāng)前的絕對路徑為目錄:
file_display(absolute_path)
file_display('/home/pushy')
這樣我們就可以遍歷到/home/pushy路徑下的所有文件:
另外我們還可以使用遞歸來創(chuàng)建目錄:
import os
def createFile(dirname):
exits = os.path.exists(dirname)
if exits:
return True
else:
# 開始遞歸調(diào)用函數(shù)鼓黔，并接受其返回值:
rec_result = createFile(os.path.dirname(dirname))
if rec_result:
# 如果不存在該目錄，則創(chuàng)建dirname的目錄不见，并返回已經(jīng)創(chuàng)建(存在)的值True:
os.mkdir(dirname)
return True
createFile('./aa/bb/cc')
4. 循環(huán)與遞歸
好了澳化，遞歸的知識差不多介紹完了。如果看完上邊大概已經(jīng)了解了循環(huán)和遞歸的區(qū)別了稳吮。對了!簡單來說肆捕，循環(huán)是有去無回，而遞歸則是有去有回(因為存在終止條件)盖高。
舉個栗子慎陵，你用你手中的鑰匙打開一扇門眼虱，結(jié)果去發(fā)現(xiàn)前方還有一扇門，緊接著你又用鑰匙打開了這扇門席纽，然后你又看到一扇們...但是當(dāng)你開到某扇門時捏悬，發(fā)現(xiàn)前方是一堵墻無路可走了，你選擇原路返回——這就是遞歸
但是如果你打開一扇門后润梯，同樣發(fā)現(xiàn)前方也有一扇們过牙，緊接著你又打開下一扇門...但是卻一直沒有碰到盡頭——這就是循環(huán)。
