摘要：在遞歸過程中，未完成計(jì)算的函數(shù)將會(huì)掛起壓入調(diào)用堆棧，不然遞歸結(jié)束的時(shí)候沒辦法進(jìn)行回溯。這就引出了回溯法回溯法就是在達(dá)到遞歸邊界前的某層，由于一些事實(shí)導(dǎo)致已經(jīng)不需要前往任何一個(gè)子問題遞歸，就可以直接返回上一層。

遞歸在前端開發(fā)中應(yīng)用還是非常廣泛的，首先DOM就是樹狀結(jié)構(gòu)，而這種結(jié)構(gòu)使用遞歸去遍歷是非常合適的。然后就是對(duì)象和數(shù)組的深復(fù)制很多庫也是使用遞歸實(shí)現(xiàn)的例如jquery中的extend方法。甚至在畫圖時(shí)也會(huì)經(jīng)常利用遞歸實(shí)現(xiàn)一些圖形，犀牛書中就有相關(guān)的例子。
由此可見遞歸是一個(gè)非常有用的工具，本文余下的部分將按照傳統(tǒng)的方式講述遞歸，首先由分治思想引出遞歸，因?yàn)檫f歸是實(shí)現(xiàn)分治的最為直觀的算法，然后將通過幾個(gè)經(jīng)典的例子如斐波那契數(shù)列、階乘、全排和n皇后來一步步深入了解遞歸。最終我們將回歸前端，使用遞歸解決一些問題，如實(shí)現(xiàn)深復(fù)制、遍歷dom樹等。

這里主要引用《算法筆記》里的定義（其實(shí)這個(gè)系列算是這本書的讀書筆記吧。。）

分治（divide and conquer）全稱分而治之，即分治法將原問題劃分為若干個(gè)規(guī)模較小兒結(jié)構(gòu)與原問題相同或者相似的子問題，然后分別解決這些子問題，最后合并子問題的解，即可得到原問題的解

步驟：

注意：

分解的子問題應(yīng)該相互獨(dú)立、沒有交叉。不然應(yīng)該選擇其它解決方法。

分治是一種思想，既可以使用遞歸也可以使用非遞歸手段實(shí)現(xiàn)

遞歸就是反復(fù)調(diào)用自身函數(shù)，但每次調(diào)用時(shí)會(huì)吧范圍縮小，直到范圍縮小到可以直接得到邊界數(shù)據(jù)的結(jié)果，然后在返回的路上求出對(duì)應(yīng)的解。
由分治和遞歸的定義就可以看出，遞歸是實(shí)現(xiàn)分治的最直觀的算法。
遞歸式的重要概念：

遞歸邊界：沒有遞歸邊界會(huì)導(dǎo)致無限遞歸，然后就會(huì)報(bào)錯(cuò) Maximum call stack size exceeded

遞歸式

下面通過幾個(gè)例子來深入了解一下遞歸：

n!的計(jì)算公式：
$$ n!=1*2*3*.....*n $$
n!的遞歸式：
$$ F(n)=F(n-1)*n $$
有了遞歸式就可以很方便的寫出遞歸函數(shù)：

 function F(n=3){
       if(n==0) return 1;
        else return F(n-1)*n;
    }
    console.log(F())

為了方便理解，這里選取了3！數(shù)量較少遞歸過程好畫，同時(shí)給出了圖來描述這個(gè)遞歸過程：

同時(shí)我們結(jié)合實(shí)際執(zhí)行時(shí)的gif來動(dòng)態(tài)的了解一下：

這里著重注意一下最右側(cè)的Call Stack,俗稱調(diào)用堆棧，這個(gè)堆棧有個(gè)特點(diǎn)就是后進(jìn)先出（LILO），調(diào)用堆棧存放的是函數(shù)。在遞歸過程中，未完成計(jì)算的函數(shù)將會(huì)掛起（壓入調(diào)用堆棧），不然遞歸結(jié)束的時(shí)候沒辦法進(jìn)行回溯。圖一里的四層就對(duì)應(yīng)Call Stack里放的四個(gè)F，然后我們?cè)儆^察一下那個(gè)變量n，每次單步執(zhí)行的時(shí)候n都在變化，步驟1時(shí)n=2...步驟3時(shí)n=0，當(dāng)n=0的時(shí)候達(dá)到了當(dāng)前的遞歸邊界，結(jié)果開始返回，這時(shí)我們觀察Call Stack下方的Scope：

那個(gè)紅框標(biāo)識(shí)出來的變量Return value,這時(shí)就開始進(jìn)入回溯階段，就是步驟4至步驟7，Call Stack開始彈出之前保存的遞歸函數(shù)，每次都返回一個(gè)計(jì)算好的值，最后合并成最終結(jié)果。

Fibonacci數(shù)列是滿足F(0)=1,F(1)=1,F(n)=F(n-1)+F(n-2)(n>=2)的數(shù)列。因此可以得出

遞歸邊界：為F(0)=1,F(1)=1

遞歸式：為F(n)=F(n-1)+F(n-2)(n>=2)

從上面可以看出和3.1中的階乘很像，我們參照著就可很快寫出：

 function Fib(n=4){
        if(n==0||n==1) return 1;
        else return Fib(n-1)+Fib(n-2);
    }
    console.log(Fib())

現(xiàn)在畫一下它的遞歸樹

黑線是遞歸函數(shù)入棧，黃線是出棧，步驟1~17表示順序。從這種圖中我們可以小窺一下畫同時(shí)調(diào)用多個(gè)自己的遞歸樹的方法，因?yàn)榇a都是順序執(zhí)行的，所以遞歸也要按順序入棧出棧，遇到這種情況就先指著優(yōu)先級(jí)最高的那個(gè)一直遞歸到遞歸邊界，然后在返回的過程中按順序遞歸剩下的即可。

引用百度百科的解釋：

從n個(gè)不同元素中任取m（m≤n）個(gè)元素，按照一定的順序排列起來，叫做從n個(gè)不同元素
 中取出m個(gè)元素的一個(gè)排列。當(dāng)m=n時(shí)所有的排列情況叫全排列。
公式：全排列數(shù)f(n)=n!(定義0!=1)，如1,2,3三個(gè)元素的全排列為：
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
共3*2*1=6種。

本例使用的是字典序（從小到大順序排序）實(shí)現(xiàn)全排，而上段中的1，2，3的全排就是按照字典序排列的。
從遞歸角度分析，輸出n的全排就可以分解為輸出以1開頭的全排、2開頭的全排.....輸出以n開頭的全排。
定義數(shù)組save用于存放當(dāng)前的排列，設(shè)定一個(gè)flag數(shù)組當(dāng)flag[x]為true時(shí)表示整數(shù)x已經(jīng)存在save中，當(dāng)遞歸結(jié)束時(shí)需要還原。index表示排列位置。遞歸邊界就是index==n+1，表示1~n位置都已經(jīng)填好。

function Permutation(n) {
        let flag = new Array(n + 1).fill(false);
        let save = new Array(n + 1).fill(0);
        let index = 1;
        return (function innerPer(index) {
            if (index == n + 1) {
                for (let i = 1; i <= n; i++) {
                    console.log(save[i]);
                }
                console.log("
")
                return;
            }
            for (let x = 1; x <= n; x++) {
                if (!flag[x]) {
                    flag[x] = true;//每向下遞歸一次，進(jìn)入if的次數(shù)少一
                    save[index] = x;//index在每層循環(huán)過程中是不變的
                    innerPer(index + 1);//僅在遞歸時(shí)發(fā)生變化
                    flag[x] = false;//遞歸結(jié)束還原狀態(tài)
                }
            }
        })(index)
    }

    Permutation(3);

這個(gè)是正序輸出，大家也可以實(shí)現(xiàn)一下逆序輸出，或者畫一畫遞歸樹加深一下印象。

n皇后問題很經(jīng)典，該問題指的是在n*n的棋盤上放置n個(gè)皇后，使得這n個(gè)皇后不再同一行、同一列、同一對(duì)角線上，求合法的方案數(shù)量，下圖就是n=5的一個(gè)合法方案。

因?yàn)槊恳恍忻恳涣兄荒芊胖靡粋€(gè)皇后，所以這個(gè)問題就轉(zhuǎn)換為n的排列問題，例如上圖按照行號(hào)就是24513。這樣我們把3.3中的代碼稍作修改就能解決現(xiàn)在的問題。（所以說數(shù)學(xué)好的人就是nb，唉。。）
我們?cè)谌诺拇a上加上判斷每兩個(gè)皇后是否在對(duì)角線上的代碼即可。

 function Queen(n) {
        let flag = new Array(n + 1).fill(false);
        let save = new Array(n + 1).fill(0);
        let index = 1;
        let cnt = 0;

        return (function innerQ(index) {
            if (index == n + 1) {
                let judge = true;
                for (let i = 1; i <= n; i++) {
                    for (let j = i + 1; j <= n; j++) {
                        if (Math.abs(i - j) == Math.abs(save[i] - save[j])) {
                            judge = false;
                        }
                    }
                }
                if (judge) {
                    console.log(save, ++cnt);
                    console.log("
");

                }
                return;
            }
            for (let x = 1; x <= n; x++) {
                if (!flag[x]) {
                    flag[x] = true;
                    save[index] = x;
                    innerQ(index + 1);
                    flag[x] = false;
                }
            }
        })(index)

    }
    Queen(10)

這里有個(gè)問題就是判斷對(duì)角線沖突，這里采用兩個(gè)一維數(shù)組解決了二維數(shù)組的問題，外層的for循環(huán)i，j為列號(hào)，一位數(shù)組里存的值為行號(hào)，通過觀察可以知道，如果兩個(gè)棋盤格子處在對(duì)角的位置，那么他們的橫坐標(biāo)之差等于他們的縱坐標(biāo)之差的絕對(duì)值（斜字部分引用自《運(yùn)用全排列的方法解決八皇后問題》）。
上面這種枚舉所有情況然后挨個(gè)判斷合法性的手段被稱之為暴力法，通過觀察可以發(fā)現(xiàn)只要發(fā)現(xiàn)第一次不合法那整個(gè)遞歸就可以返回，無須將遞歸進(jìn)行到底再去判斷，直接返回上層即可。這就引出了回溯法
回溯法就是在達(dá)到遞歸邊界前的某層，由于一些事實(shí)導(dǎo)致已經(jīng)不需要前往任何一個(gè)子問題遞歸，就可以直接返回上一層。
下面舉出回溯法的代碼，請(qǐng)與上方進(jìn)行對(duì)比。

    function ReQueen(n) {
        let flag = new Array(n + 1).fill(false);
        let save = new Array(n + 1).fill(0);
        let index = 1;
        let cnt = 0;

        return (function innerQ(index) {
            if (index == n + 1) {
                console.log(save, ++cnt);
                return;
            }
            for (let x = 1; x <= n; x++) {
                if (!flag[x]) {
                    let judge = true;
                    for (let pre = 1; pre < index; pre++) {//再次強(qiáng)調(diào)index代表位置
                        if (Math.abs(pre - index) == Math.abs(save[pre] - x)) {
                            judge = false;
                            break;
                        }
                    }
                    if (judge) {
                        flag[x] = true;
                        save[index] = x;
                        innerQ(index + 1);
                        flag[x] = false;
                    }
                }
            }
        })(index)
    }

    ReQueen(8)

遞歸在前端中應(yīng)用還是非常常見的。主要原因是前端數(shù)據(jù)量一般不大，而且從es6開始支持尾遞歸的優(yōu)化。同時(shí)DOM也是樹狀結(jié)構(gòu)，在遍歷樹這種數(shù)據(jù)結(jié)構(gòu)的時(shí)候也常用遞歸。所以相對(duì)與前面講的哈希，遞歸是要重點(diǎn)掌握的。

在使用textContent和innerText時(shí)有時(shí)并不能滿足我們的要求，這時(shí)我們就要手工的收集文本來得到想要的結(jié)果。

function GetText(elem){
        var text="";
        var length = elem.childNodes.length;
        for(let i=0;i
3.5.2使用遞歸實(shí)現(xiàn)屬性查詢
原生的js并不提供通過標(biāo)簽屬性去獲取標(biāo)簽，在這里我們通過遞歸遍歷dom樹去實(shí)現(xiàn)這個(gè)功能。
首先我們要實(shí)現(xiàn)遞歸遍歷dom樹
function WalkDom(node, func) {
        func(node);//首先把傳入的節(jié)點(diǎn)，傳給func進(jìn)行操作
        node = node.firstChild;//提取節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn)
        while (node) {//遞歸的終止條件就是節(jié)點(diǎn)不存在
            WalkDom(node, func);//遞歸
            node = node.nextSibling;//獲取兄弟節(jié)點(diǎn)
        }
    }
這里的遞歸終止條件就是節(jié)點(diǎn)不存在。
現(xiàn)在實(shí)現(xiàn)通過屬性獲取標(biāo)簽，這里主要用到的是原生方法getAttribute
function getElementByAttr(attr, value ,node=document.body) {//兩個(gè)可選參數(shù)，屬性對(duì)應(yīng)的值value，指定范圍節(jié)點(diǎn)node
        let res = [];
        WalkDom(node, function (node) {
            let actual = node.nodeType == 1 && node.getAttribute(attr);//這里主要用到&&運(yùn)算的特點(diǎn)，第一個(gè)值為真則返回第二個(gè)值，第一個(gè)值為假則返回第一個(gè)值，第二個(gè)表達(dá)式將不進(jìn)行計(jì)算
            if (typeof actual == "string" && (actual === value || typeof value != "string")) {
                res.push(node);
            }
        })
        return res;
    }
3.5.3使用遞歸實(shí)現(xiàn)深復(fù)制
因?yàn)閖s存在引用型（對(duì)象和數(shù)組都是引用型），引用型的有一個(gè)特點(diǎn)就是復(fù)制上分為淺復(fù)制和深復(fù)制。淺復(fù)制和深復(fù)制的區(qū)別如下：
var a=[1,2,3],b=a,c=[];//把a(bǔ)直接賦值給b的這種情況就是淺復(fù)制
    b.pop();//修改b的同時(shí)a也被改變了
    console.log(a);//輸出[1,2]
    a.forEach(function(elem,index){
        c[index]=elem
    })
    c.push(4)//修改c，不影響a
    console.log(a,c)
js的引用型在賦值的時(shí)候，賦給變量的可能是地址，而非數(shù)據(jù)的副本。因?yàn)樵谑褂脭?shù)組和對(duì)象的時(shí)候經(jīng)常嵌套數(shù)組或?qū)ο笏晕覀円ㄟ^遞歸的方式來實(shí)現(xiàn)數(shù)據(jù)的備份。
function DeepClone(obj){
        if(!obj||typeof obj!=="object")
            return obj;
        var tmp =new obj.constructor();
        for(let key in obj){
            tmp[key]=DeepClone(obj[key]);
        }
        return tmp;
    }
   var cc=[[1,2,4],{"dd":123}],bb=DeepClone(cc)
    console.log(bb.pop(),cc)
這是一個(gè)簡陋的實(shí)現(xiàn)，看那個(gè)類型判斷就可以看出來很不嚴(yán)謹(jǐn)，不過大部分庫都提供有完備的深復(fù)制的方法。例如jq的extend就可以實(shí)現(xiàn)深復(fù)制。
4小結(jié)
和js相關(guān)的例子還是太少太理論化，未來會(huì)增加一些更接地氣的。
樹和圖結(jié)構(gòu)也會(huì)用到遞歸，所以遞歸這一節(jié)請(qǐng)深入研究一下。
參考
《算法筆記》
《javascript函數(shù)式編程》
《javascript語言精粹》
《javascript忍者秘籍》