[[376839]]

遞歸和尾遞歸

簡(jiǎn)單的說(shuō)，遞歸就是函數(shù)自己調(diào)用自己，它做為一種算法在程序設(shè)計(jì)語(yǔ)言中廣泛應(yīng)用。其核心思想是把一個(gè)大型復(fù)雜的問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解。一般來(lái)說(shuō)，遞歸需要有邊界條件、遞歸前進(jìn)階段和遞歸返回階段。當(dāng)邊界條件不滿足時(shí)，遞歸前進(jìn);當(dāng)邊界條件滿足時(shí)，遞歸返回。

但是作為一個(gè)合格的程序員，我們也因該知道，遞歸算法相對(duì)常用的算法如普通循環(huán)等，運(yùn)行效率較低。因此，應(yīng)該盡量避免使用遞歸，除非沒(méi)有更好的算法或者某種特定情況，遞歸更為適合的時(shí)候。在遞歸調(diào)用的過(guò)程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開辟了棧來(lái)存儲(chǔ)，遞歸次數(shù)過(guò)多容易造成棧溢出等。

這個(gè)時(shí)候，我們就需要用到尾遞歸，即一個(gè)函數(shù)中所有遞歸形式的調(diào)用都出現(xiàn)在函數(shù)的末尾，對(duì)于尾遞歸來(lái)說(shuō)，由于只存在一個(gè)調(diào)用記錄，所以永遠(yuǎn)不會(huì)發(fā)生"棧溢出"錯(cuò)誤。

function factorial(n) { 
  if (n === 1) return 1; 
  return n * factorial(n - 1); 
} 
 
factorial(5) // 120 

最多需要保存n個(gè)調(diào)用棧，復(fù)雜度 O(n)，如果我們使用尾遞歸：

function factorial(n, total = 1) { 
  if (n === 1) return total; 
  return factorial(n - 1, n * total); 
} 
 
factorial(5) // 120 

此時(shí)只需要保存一個(gè)調(diào)用棧，復(fù)雜度 O(1) 。通過(guò)這個(gè)案例，你是否已經(jīng)慢慢理解其精髓了呢?接下來(lái)我將介紹幾個(gè)常用的遞歸應(yīng)用的案例，并在其后實(shí)現(xiàn)本文標(biāo)題剖出的樹的實(shí)現(xiàn)。

遞歸的常用應(yīng)用案例

1. 數(shù)組求和

對(duì)于已知數(shù)組arr，求arr各項(xiàng)之和。

function sumArray(arr, total) { 
    if(arr.length === 1) { 
        return total 
    } 
    return sum(arr, total + arr.pop()) 
} 
 
let arr = [1,2,3,4]; 
sumArray(arr, arr[1]) // 10 

該方法給函數(shù)傳遞一個(gè)數(shù)組參數(shù)和初始值，也就是數(shù)組的第一項(xiàng)，通過(guò)迭代來(lái)實(shí)現(xiàn)數(shù)組求和。

2. 斐波那且數(shù)列

斐波那契數(shù)列(Fibonacci sequence)，又稱黃金分割數(shù)列，指的是這樣一個(gè)數(shù)列：1、1、2、3、5、8、13、21、34、……在數(shù)學(xué)上，斐波那契數(shù)列以如下被以遞推的方法定義：F(1)=1，F(xiàn)(2)=1, F(n)=F(n-1)+F(n-2)(n>=3，n∈N*)在現(xiàn)代物理、準(zhǔn)晶體結(jié)構(gòu)、化學(xué)等領(lǐng)域，斐波納契數(shù)列都有直接的應(yīng)用。接下來(lái)我們用js實(shí)現(xiàn)一個(gè)求第n個(gè)斐波那契數(shù)的方法：

// 斐波那契數(shù)列 
function factorial1 (n) { 
    if(n <= 2){ 
        return 1 
    } 
    return factorial1(n-1) + factorial1(n-2) 
} 
 
// 尾遞歸優(yōu)化后 
function factorial2 (n, start = 1, total = 1) { 
    if(n <= 2){ 
        return total 
    } 
    return factorial2 (n -1, total, total + start) 
} 

由尾遞歸優(yōu)化后的函數(shù)可以知道，每一次調(diào)用函數(shù)自身，都會(huì)將更新后的初始值和最終的結(jié)果傳遞進(jìn)去，通過(guò)回溯來(lái)求得最終的結(jié)果。

3. 階乘

階乘在上文以提到過(guò)，如想回顧，請(qǐng)向上翻閱。

4. 省市級(jí)聯(lián)多級(jí)聯(lián)動(dòng)

省市級(jí)聯(lián)多級(jí)聯(lián)動(dòng)的方法本質(zhì)是生成結(jié)構(gòu)化的數(shù)據(jù)結(jié)構(gòu)，在element或antd中都有對(duì)應(yīng)的實(shí)現(xiàn)，這里就不做過(guò)多介紹了。

5. 深拷貝

深拷貝的例子大家也已經(jīng)司空見慣了，這里只給出一個(gè)簡(jiǎn)單的實(shí)現(xiàn)思路：

function clone(target) { 
   if (typeof target === 'object') { 
       let cloneTarget = Array.isArray(target) ? [] : {}; 
       for (const key in target) { 
           cloneTarget[key] = clone(target[key]); 
       } 
       return cloneTarget; 
   } else { 
       return target; 
   } 
}; 

6. 爬梯問(wèn)題

一共有n個(gè)臺(tái)階，每次只能走一個(gè)或兩個(gè)臺(tái)階，問(wèn)要走完這個(gè)臺(tái)階，一共有多少種走法。

n =1; result = 1  --> 1 
n =2; result = 2  --> 11 2 
n =3; result = 3  --> 111 12 21 
... 
如果第一步走1個(gè)臺(tái)階，由以上規(guī)律可以發(fā)現(xiàn)剩下的臺(tái)階有n-1種走法； 
如果第一步走2個(gè)臺(tái)階，由以上規(guī)律可以發(fā)現(xiàn)剩下的臺(tái)階有n-2種走法； 
則一共有fn(n-1) + fn(n-2) 種走法 
function steps(n) { 
    if(n <= 1) { 
        return 1 
    } 
    return steps(n-1) + steps(n-2) 
} 

7. 對(duì)象數(shù)據(jù)格式化

這道題是本人曾經(jīng)面試阿里的一道筆試題，問(wèn)題是如果服務(wù)器返回了嵌套的對(duì)象，對(duì)象鍵名大小寫不確定，如果統(tǒng)一讓鍵名小寫。

let obj = { 
    a: '1', 
    b: { 
        c: '2', 
        D: { 
            E: '3' 
        } 
    } 
} 
轉(zhuǎn)化為如下： 
let obj = { 
    a: '1', 
    b: { 
        c: '2', 
        d: { 
            e: '3' 
        } 
    } 
} 
 
// 代碼實(shí)現(xiàn) 
function keysLower(obj) { 
    let reg = new RegExp("([A-Z]+)", "g"); 
    for (let key in obj) { 
        if (obj.hasOwnProperty(key)) { 
            let temp = obj[key]; 
            if (reg.test(key.toString())) { 
                // 將修改后的屬性名重新賦值給temp，并在對(duì)象obj內(nèi)添加一個(gè)轉(zhuǎn)換后的屬性 
                temp = obj[key.replace(reg, function (result) { 
                    return result.toLowerCase() 
                })] = obj[key]; 
                // 將之前大寫的鍵屬性刪除 
                delete obj[key]; 
            } 
            // 如果屬性是對(duì)象或者數(shù)組，重新執(zhí)行函數(shù) 
            if (typeof temp === 'object' || Object.prototype.toString.call(temp) === '[object Array]') { 
                keysLower(temp); 
            } 
        } 
    } 
    return obj; 
}; 

具體過(guò)程和思路在代碼中已經(jīng)寫出了注釋，感興趣可以自己研究一下。

8. 遍歷目錄/刪除目錄

我們這里使用node來(lái)實(shí)現(xiàn)刪除一個(gè)目錄，用現(xiàn)有的node API確實(shí)有刪除目錄的功能，但是目錄下如果有文件或者子目錄，fs.rmdir && fs.rmdirSync 是不能將其刪除的，所以要先刪除目錄下的文件，最后再刪除文件夾。

function deleteFolder(path) { 
    var files = []; 
    if(fs.existsSync(path)) { // 如果目錄存在 
        files = fs.readdirSync(path); 
        files.forEach(function(file,index){ 
            var curPath = path + "/" + file; 
            if(fs.statSync(curPath).isDirectory()) { // 如果是目錄，則遞歸 
                deleteFolder(curPath); 
            } else { // 刪除文件 
                fs.unlinkSync(curPath); 
            } 
        }); 
        fs.rmdirSync(path); 
    } 
} 

9. 繪制分形圖形

通過(guò)遞歸，我們可以在圖形學(xué)上有更大的自由度，但是請(qǐng)記住，并不是最好的選擇。

我們可以借助一些工具和遞歸的思想，實(shí)現(xiàn)如上的分形圖案。

 10. 扁平化數(shù)組Flat

數(shù)組拍平實(shí)際上就是把一個(gè)嵌套的數(shù)組，展開成一個(gè)數(shù)組，如下案例：

let a = [1,2,3, [1,2,3, [1,2,3]]] 
// 變成 
let a = [1,2,3,1,2,3,1,2,3] 
// 具體實(shí)現(xiàn) 
function flat(arr = [], result = []) { 
    arr.forEach(v => { 
        if(Array.isArray(v)) { 
            result = result.concat(flat(v, [])) 
        }else { 
            result.push(v) 
        } 
    }) 
    return result 
} 
 
flat(a) 

當(dāng)然這只是筆者實(shí)現(xiàn)的一種方式，更多實(shí)現(xiàn)方式等著你去探索。

用遞歸畫一棵自定義風(fēng)格的結(jié)構(gòu)樹

通過(guò)上面的介紹，我想大家對(duì)遞歸及其應(yīng)用已經(jīng)有一個(gè)基本的概念，接下來(lái)我將一步步的帶大家用遞歸畫一棵結(jié)構(gòu)樹。效果圖：

該圖形是根據(jù)目錄結(jié)構(gòu)生成的目錄樹圖，在很多應(yīng)用場(chǎng)景中被廣泛使用，接下來(lái)我們就來(lái)看看他的實(shí)現(xiàn)過(guò)程吧：

const fs = require('fs') 
const path = require('path') 
// 遍歷目錄/生成目錄樹 
function treeFolder(path, flag = '|_') { 
    var files = []; 
     
    if(fs.existsSync(path)) { 
        files = fs.readdirSync(path); 
        files.forEach(function(file,index){ 
            var curPath = path + "/" + file; 
            if(fs.statSync(curPath).isDirectory()) { // recurse 
                // obj[file] = treeFolder(curPath, {}); 
                console.log(flag, file) 
                treeFolder(curPath, '   ' + flag) 
            } else { 
                // obj['--'] = file 
                console.log(flag, file) 
            } 
        }) 
        // return obj 
    } 
} 
 
treeFolder(path.resolve(__dirname, './test')) 

test為我們建的測(cè)試目錄，如下：

我們通過(guò)短短10幾行代碼就實(shí)現(xiàn)了一個(gè)生成結(jié)構(gòu)樹的小應(yīng)用，是不是感覺(jué)遞歸有點(diǎn)意思呢?在這個(gè)函數(shù)中，第一個(gè)參數(shù)是目錄的絕對(duì)路徑，第二個(gè)是標(biāo)示符，標(biāo)示符決定我們生成的樹枝的樣式，我們可以自定義不同的樣式。