摘要：在遞歸過程中，未完成計算的函數將會掛起壓入調用堆棧，不然遞歸結束的時候沒辦法進行回溯。這就引出了回溯法回溯法就是在達到遞歸邊界前的某層，由于一些事實導致已經不需要前往任何一個子問題遞歸，就可以直接返回上一層。

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

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

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

步驟：

注意：

分解的子問題應該相互獨立、沒有交叉。不然應該選擇其它解決方法。

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

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

遞歸邊界：沒有遞歸邊界會導致無限遞歸，然后就會報錯 Maximum call stack size exceeded

遞歸式

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

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

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

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

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

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

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

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

遞歸邊界：為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)在畫一下它的遞歸樹

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

引用百度百科的解釋：

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

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

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;//每向下遞歸一次，進入if的次數少一
                    save[index] = x;//index在每層循環(huán)過程中是不變的
                    innerPer(index + 1);//僅在遞歸時發(fā)生變化
                    flag[x] = false;//遞歸結束還原狀態(tài)
                }
            }
        })(index)
    }

    Permutation(3);

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

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

因為每一行每一列只能放置一個皇后，所以這個問題就轉換為n的排列問題，例如上圖按照行號就是24513。這樣我們把3.3中的代碼稍作修改就能解決現(xiàn)在的問題。（所以說數學好的人就是nb，唉。。）
我們在全排的代碼上加上判斷每兩個皇后是否在對角線上的代碼即可。

 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)

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

    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++) {//再次強調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)

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

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

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