你好！歡迎閱讀我的博文，你可以跳轉(zhuǎn)到我的個(gè)人博客網(wǎng)站，會(huì)有更好的排版效果和功能。
此外，本篇博文為本人Pushy原創(chuàng)，如需轉(zhuǎn)載請注明出處：https://pushy.site/posts/1519818136

一說起遞歸,我想每個(gè)人都不陌生.舉個(gè)從小就聽過的例子:從前有座山,山里有座廟,廟里有個(gè)和尚,和尚在講故事,從前有座山,山里有座廟,廟里有個(gè)和尚,和尚在講故事,從前有座山...,還有你從兩面相對的鏡子中看到的畫面,其實(shí)都是抽象出來的遞歸現(xiàn)象,但是嚴(yán)格來說并不是遞歸,因?yàn)闀?huì)一直重復(fù)下去,沒有終止條件,那就稱為死循環(huán)了.有關(guān)遞歸和死循環(huán)的異同我們之后會(huì)說到,那么現(xiàn)在先來了解一下什么是遞歸?

那么什么是遞歸呢? 要理解遞歸,就得先了解什么是遞歸,實(shí)際上這句話就是一個(gè)遞歸.這么說可能不好理解,接下來我舉個(gè)簡單的例子來解釋這段話的意義.

假設(shè)我們現(xiàn)在都不知道什么是遞歸,我們自然想到打開瀏覽器,輸入到谷歌的網(wǎng)頁,我們點(diǎn)擊搜索遞歸,然后我們在為維基百科中了解到了遞歸的基本定義,在了解到了遞歸實(shí)際上是和棧有關(guān)的時(shí)候,你又蒙圈了,什么是棧呢?數(shù)據(jù)結(jié)構(gòu)沒學(xué)清楚,此時(shí)的你只能又打開谷歌,搜索什么是棧.接下來你依次了解了內(nèi)存/操作系統(tǒng).在你基本了解好知識(shí)之后,你通過操作系統(tǒng)了解了內(nèi)存,通過內(nèi)存了解了棧,通過棧了解了什么是遞歸這下你恍然大悟!原來這就是遞歸啊!

這下應(yīng)該有點(diǎn)明白了吧,這個(gè)過程其實(shí)就是遞歸的過程,如果不了解遞歸,那就先了解什么是遞歸,可能你會(huì)說這是個(gè)循環(huán)并不是遞歸,我們前面說到,遞歸是需要終止條件的,那么你明白遞歸是什么其實(shí)就是終止條件.整個(gè)過程,搜索引擎充當(dāng)遞歸函數(shù)(只是形象的假設(shè));在你去依次查找遞歸/棧/內(nèi)存/操作系統(tǒng)的過程為前行階段,在你都了解完之后,反回去了解含義的過程為退回階段.如果還是不太清楚,可以接著看下面的例子

2. 示例:

也許之前你在網(wǎng)絡(luò)上看到過這張圖片:

image

實(shí)際上這張圖就很形象地表達(dá)出了遞歸,這句嚇得我抱起了抱著抱著抱著我的小鯉魚的我的我的我如果從字面意義上看可能看不出是什么意思,那么我們可以通過代碼來實(shí)現(xiàn)同樣的效果:

function Recursion(depth) {
    console.log('抱著');
    if (!depth) {
        console.log('我的小鯉魚')
    } else {
        Recursion(--depth);  // 遞歸調(diào)用
    }
    console.log('的我');
}

console.log('嚇得我抱起了');
Recursion(2)

在終端的打印結(jié)果為如下,可以看到和上面的那段話是一樣的:

image

代碼其實(shí)十分簡單,但是需要理解的是:if代碼塊的條件(!depth)為遞歸調(diào)用的終止條件,在else代碼塊內(nèi)遞歸調(diào)用函數(shù).我們前面有說到遞歸的過程是存在前行和退回階段的,那么在前行階段我們在每次調(diào)用函數(shù)后,打印出了"抱著",并且當(dāng)depth≠0時(shí)重新調(diào)用該函數(shù);在退回階段,將會(huì)去執(zhí)行代碼console.log('的我');再打印出"的我".

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

image

好了!這下你應(yīng)該明白什么是遞歸了吧?如果你還沒有明白什么是遞歸的話,你可以看這里

3. 應(yīng)用:

3.1 斐波拉契數(shù)列:

有關(guān)遞歸應(yīng)用的應(yīng)用有很多,例如注明的斐波拉契數(shù)列就可以通過遞歸來實(shí)現(xiàn):

def fib(x):
    if x < 2:
        return 0 if x == 0 else 1
    # 當(dāng)x > 2時(shí),開始遞歸調(diào)用fib()函數(shù):
    return fib(x - 1) + fib(x - 2)

print(fib(6))  # 打印結(jié)果為:8

這里需要對i<2時(shí)的特殊情況做出判斷,當(dāng)x==0時(shí),直接返回0,當(dāng)x==1時(shí),直接返回1

3.2 遍歷文件:

首先我們需要了解遍歷的算法:定義的file_display函數(shù)以某個(gè)目錄(/home/pushy)作為遍歷的起點(diǎn).遇到一個(gè)子目錄時(shí),就先接著遍歷子目錄(遞歸調(diào)用函數(shù));遇到一個(gè)文件時(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路徑下的所有文件:

[圖片上傳失敗...(image-f65805-1519134227254)]

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

好了,遞歸的知識(shí)差不多介紹完了.如果看完上邊大概已經(jīng)了解了循環(huán)和遞歸的區(qū)別了.對了!簡單來說,循環(huán)是有去無回,而遞歸則是有去有回(因?yàn)榇嬖诮K止條件).

舉個(gè)栗子,你用你手中的鑰匙打開一扇門,結(jié)果去發(fā)現(xiàn)前方還有一扇門,緊接著你又用鑰匙打開了這扇門,然后你又看到一扇們...但是當(dāng)你開到某扇門時(shí),發(fā)現(xiàn)前方是一堵墻無路可走了,你選擇原路返回.這就是遞歸

但是如果你打開一扇門后,同樣發(fā)現(xiàn)前方也有一扇們,緊接著你又打開下一扇門...但是卻一直沒有碰到盡頭,這就是循環(huán).

參考資料:

[知乎]什么是遞歸

七天學(xué)會(huì)NodeJs--遞歸算法