1.介紹

一說起遞歸，我想每個人都不陌生。舉個從小就聽過的例子：從前有座山，山里有座廟，廟里有個和尚，和尚在講故事，從前有座山，山里有座廟，廟里有個和尚，和尚在講故事，從前有座山...
還有你從兩面相對的鏡子中看到的畫面，其實都是抽象出來的遞歸現(xià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ò)上看到過這張圖片：

image.png

實際上這張圖很形象地表達出了遞歸，這句嚇得我抱起了抱著抱著抱著我的小鯉魚的我的我的我如果從字面義上看可能看不出是什么意思，那么我們可以通過代碼來實現(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('的我');再打印出"的我".

褚躍躍的圖也能比較清楚地反映出這個過程:

image.png

好了！這下你應(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ù))。遇到一個文件時，就直接對改文件進行操作(這里只打印出文件的文件名):

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路徑下的所有文件:

5b6fac208b78a.png

另外我們還可以使用遞歸來創(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)。