遞歸

遞歸是一種解決問(wèn)題的方法，它解決問(wèn)題的各個(gè)小部分抢肛，直到解決最初的大問(wèn)題熬芜，遞歸通常涉及到函數(shù)的自身調(diào)用福稳。
遞歸函數(shù)是像下面這樣能夠直接調(diào)用自身的方法或是函數(shù)：

function recursiveFunction(someParam){
  recursiveFunction(someParam);
}

當(dāng)然灵寺，像下面這樣間接的調(diào)用自己的函數(shù)也是遞歸函數(shù)：

function recursiveFunction1(someParam){
  recursiveFunction2(someParam);
}

function recursiveFunction2(someParam){
  recursiveFunction1(someParam);
}

當(dāng)然我們執(zhí)行一個(gè)函數(shù)毁枯，是為了實(shí)現(xiàn)某一個(gè)目的叮称，所以我們一定要給該函數(shù)一個(gè)跳出的條件瓤檐，也就是說(shuō)每一個(gè)遞歸函數(shù)都必須要有邊界條件挠蛉，即不再遞歸調(diào)用的條件（停止點(diǎn)）谴古，防止無(wú)限遞歸下去掰担。
JavaScript調(diào)用棧大小的限制
如果忘記停止遞歸調(diào)用的邊界條件带饱，遞歸調(diào)用并不無(wú)限的執(zhí)行下去勺疼；瀏覽器會(huì)直接拋出錯(cuò)誤，也就是我們所謂的棧溢出錯(cuò)誤酪耕。
每一個(gè)瀏覽器都有自己的上限因妇。

let i = 0;
function recursiveFn(){
  i++;
  recursiveFn(); // {1}
}
try{
  recursiveFn();
}catch(ex){
  alert('i = ' + i + ' error :' +ex);
}

執(zhí)行的時(shí)候會(huì)報(bào)下面的bug：

棧溢出錯(cuò)誤

在ES6中有尾調(diào)用，如果函數(shù)最后一個(gè)操作是調(diào)用函數(shù)址芯，也就是{1}這行代碼窜觉，會(huì)通過(guò)"跳轉(zhuǎn)指令"，而不是“子程序調(diào)用”來(lái)控制旬陡，也就是說(shuō)嗎描孟，在es6中匿醒，這里的代碼是可以一直執(zhí)行下去的廉羔，所以憋他，具有停止遞歸的邊界條件是十分重要的举瑰。
斐波那契數(shù)列
我們需要先了解什么是斐波那契此迅？斐波那契數(shù)列的定義如下：

• 1和2的斐波那契數(shù)是1
• n(n > 2)的斐波那契數(shù)是(n - 1)的的斐波那契數(shù)加上(n - 2)的斐波那契數(shù)。
  現(xiàn)在讓我們開始實(shí)現(xiàn)斐波那契函數(shù):

function fibonacci(num){
  if(num === 1 || num === 2){
    return 1;
  }
}

我們的邊界條件是已知的坎怪，1和2的斐波那契是1廓握，現(xiàn)在，讓我們完成斐波那契函數(shù)的實(shí)現(xiàn)：

function fibonacci(num){
  if(num === 1 || num === 2){
    return 1;
  }
  return fibonacci(num - 1) + fibonacci(num - 2);
}

我們已經(jīng)知道闹司，當(dāng)n大于2的時(shí)候，fibonacci(n)等于fibonacci(num - 1) + fibonacci(num - 2);
現(xiàn)在我們的函數(shù)已經(jīng)編寫完成耐朴，讓我們?cè)囍页?的斐波那契函數(shù)筛峭，會(huì)產(chǎn)生如下的函數(shù)調(diào)用:

斐波那契數(shù)列的遞歸方式

當(dāng)然我們也可以通過(guò)非遞歸的方式實(shí)現(xiàn)斐波那契函數(shù):

function fib(num){
  let n1 = 1;
  let n2 = 1;
  let n = 1;
  for(let i = 3; i < num; i++){
    n = n1 +n2;
    n1 = n2;
    n2 = n;
  }
  return n; 
}

動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃（Dynamic Programmaing滨达，DP）是一種將賦值問(wèn)題分解成更小的子問(wèn)題來(lái)解決的優(yōu)化技術(shù)捡遍。
ps：我們需要注意動(dòng)態(tài)規(guī)劃和分而治之是不同的方法竹握，分而治之是將問(wèn)題分解成獨(dú)立的子問(wèn)題谓传，然后組合它們的答案续挟，而動(dòng)態(tài)規(guī)劃則是將問(wèn)題分解成互相依賴的子問(wèn)題诗祸。
我們的解決動(dòng)態(tài)規(guī)劃問(wèn)題的時(shí)候直颅，需要遵循三個(gè)重要的步驟:
(1)定義子問(wèn)題
(2)實(shí)現(xiàn)要反復(fù)執(zhí)行來(lái)解決子問(wèn)題的部分(這一步要參考前一節(jié)的遞歸的步驟)
(3)識(shí)別并求解出邊界條件
我們通過(guò)動(dòng)態(tài)規(guī)劃解決如下一些著名的問(wèn)題:背包問(wèn)題功偿、最長(zhǎng)公共子序列共耍、矩陣鏈相乘吨瞎、硬幣找零、圖的全源最短路徑关拒。

• 背包問(wèn)題：給出一組項(xiàng)目，各自有值和容量庸娱，目標(biāo)是找出總值最大的項(xiàng)目的集合着绊，這個(gè)問(wèn)題的限制是，總?cè)萘勘仨毿∮诘扔诒嘲娜萘俊?/li>
• 最長(zhǎng)公共子序列：找出一組序列最長(zhǎng)的公共子序列(可由另一序列刪除元素但是不改變余下元素的順序而得到)熟尉。
• 矩陣鏈相乘：給出一系列的矩陣归露，目標(biāo)是找到這些矩陣相乘的最高效辦法（計(jì)算次數(shù)盡可能的少），相乘操作不會(huì)進(jìn)行斤儿，解決方案是找到這些矩陣各自相乘的順序剧包。
• 硬幣找零：給出面額為d1...dn的一定數(shù)量的硬幣和要找零的錢數(shù)堕油，找出多少種找零的方法。
  圖的全源最短路徑：對(duì)所有的頂點(diǎn)對(duì)(u,v)，找出從頂點(diǎn)u到頂點(diǎn)v的最短路徑。

最少硬幣找零問(wèn)題
最少硬幣找零問(wèn)題是硬幣找零問(wèn)題的一個(gè)變種，硬幣找零問(wèn)題是給出要找零的錢數(shù)幌缝，以及可以使用的硬幣面額d1...dn及其數(shù)量轿偎，找出多少種找零的方式，最少硬幣找零問(wèn)題是給出要找零的錢數(shù)，以及可用的硬幣面額d1...dn及其數(shù)量，找到所需的最少的硬幣的個(gè)數(shù)。
例題：美國(guó)有以下的面額的硬幣：d1 = 1,d2 = 5,d3 = 10,d4 = 25
如果要找36美分的零錢施禾，我們可以用一個(gè)25美分，一個(gè)10美分肛度，和1個(gè)便士(1美分)
那我們?cè)趺磳⑦@個(gè)解答轉(zhuǎn)化為算法呢加袋？
最少的硬幣找零的解決方案就是找到n所需的最小硬幣數(shù)，但是要做到這一步，首選要找到對(duì)每個(gè)x<n的解寿谴，然后峻厚，我們將解建立在更小的值的解的基礎(chǔ)上面，讓我們來(lái)看看算法：

function MinCoinChange(coins) {
    let coins1 = coins;
    let cache = {};
    this.makeChange = function(amount) {
        let me = this;          
        if(!amount) {
            return [];
        }
        if(cache[amount]) {
            return cache[amount];
        }
        let min = [],
            newMin, newAmount;
        for(let i = 0; i < coins1.length; i++) {
            let coin = coins1[i];
            newAmount = amount - coin;
            if(newAmount >= 0) {
                newMin = me.makeChange(newAmount);
            }
            if(
              newAmount >= 0 &&
             (newMin.length < min.length - 1 || !min.length) && 
             (newMin.length || !newAmount)
              ) {
                min = [coin].concat(newMin);
                console.log('new Min' + min + ' for ' + amount);
            }
        }
        return(cache[amount] = min);
    }
}
let arr = [1, 3, 4];
let minCoinChange1 = new MinCoinChange(arr);
console.log(minCoinChange1.makeChange(6));

由上面的代碼我們看出，我們求最優(yōu)解的方法改艇，是建立在求出上一個(gè)最優(yōu)解的基礎(chǔ)上面的承疲。我們?cè)趫?zhí)行算法的過(guò)程中啊研，我們會(huì)產(chǎn)生以下的輸出：
new Min 1 for 1
new Min 1,1 for 2
new Min 1,1,1 for 3
new Min 3 for 3
new Min 1,3 for 4
new Min 4 for 4
new Min 1,4 for 5
new Min 1,1,4 for 6
new Min 3,3 for 6
[3,3]

背包問(wèn)題

背包問(wèn)題的本質(zhì)就是一個(gè)組合優(yōu)化的問(wèn)題钠绍。它可以描述如下：給定一個(gè)固定大小的本報(bào)磷脯，能夠攜帶W的背包俩功，以及一組有價(jià)值和重量的物品诡蜓，找出一個(gè)最佳的解決方案贡这，使得子昂如背包的物品重量不超過(guò)W且價(jià)值是最大的。

背包問(wèn)題描述

如果考慮背包呢鞥狗攜帶的重量只有5，對(duì)于這個(gè)例子诅挑，我們可以說(shuō)最佳的解決方案是向背包里面裝物品1和物品2，這樣咬摇，總重量為5芒珠，總價(jià)值為7.(這個(gè)問(wèn)題我們僅僅可以解決將背包里面的東西完整的裝進(jìn)來(lái)兄朋，不包括對(duì)分?jǐn)?shù)問(wèn)題無(wú)法解決，分?jǐn)?shù)的背包問(wèn)題要我們?cè)谪澬乃惴ㄖ羞M(jìn)行解決寄悯，現(xiàn)在解決的問(wèn)題是0-1背包問(wèn)題)怕膛。
具體的解決的方案，如下圖：

0-1背包的解釋

其中i表示的是物品的個(gè)數(shù)笨使，w表示的是物品的重量，在他們組成的二位的數(shù)組的值為帮坚，總的價(jià)值节视，我們看一下下面的代碼：

function knapSack (capacity,weights,values,n){
    let i,w,a,b,KS =[];
    for(i = 0; i<= n; i++){  //{1}
        KS[i] = [];
    }
    for(i = 0; i <= n; i++){
        for(w = 0; w <= capacity; w++ ){
            if(i == 0 || w == 0){ //{2}
                KS[i][w] = 0;
            }else if(weights[i - 1] <= w){ //{3}
                a = values[i - 1] + KS[i -1][w-weights[i - 1]];
                b = KS[i -1][w];
                KS[i][w] = (a > b) ? a : b; // {4} max(a,b)
            }else{
                KS[i][w] = KS [i-1][w]; //{5}
            }
        }
    }
    return KS[n][capacity]; //{6}
    }
let values = [3,4,5];
let weights = [2,3,4];
let capacity = 5;
let n = values.length;
console.log(knapSack(capacity,weights,values,n)); // 輸出為7

我們從代碼的邏輯上梳理一下這個(gè)算法是如何工作的：
行{1}：首先贞滨，初始化將用于尋找解決方案的矩陣KS[n+1][capacity]链蕊。
行{2}:忽略矩陣的第一列和第一行宴卖，只處理索引不為0的行和列
行{3}:物品i的重量必須小于約束(capacity)才有可能稱為解決方案的一部分分苇；否則沟突，總重量就會(huì)就會(huì)超出背包可以攜帶的重量簇秒，這是不可能發(fā)生的麸恍，發(fā)生這種情況的時(shí)候麦到，就要直接忽略它，用之前的值就可以了蔗衡。
行{4}:當(dāng)找到可以解決方案的物品時(shí),選擇價(jià)值大的那個(gè)。
行{6}:最后蔗怠，問(wèn)題的解決方案就在這個(gè)二維表格的右下角的最后一個(gè)格子里。
我們也看到了上面的代碼，只能輸出最大的價(jià)值，但是卻不能知道我們得到該價(jià)值的時(shí)候晚吞，背包中的重量是如何組合的缅糟，現(xiàn)在我們針對(duì)上面遇到的問(wèn)題窗宦，對(duì)代碼進(jìn)行優(yōu)化:

function findValues (n,capacity,KS,weights,values){
    let i = n, k = capacity;
    console.log('解決方案包含以下的商品：');
    while(i > 0 && k > 0){
        if(KS[i][k] !== KS[i-1][k]){
            console.log('物品' + i + '，重量'+ weights[i-1] + ',價(jià)值：' + values[i -1]);
            i--;
            k = k - KS[i][k];
        }else{
            i--;
        }
    }
}

上面的代碼在行{6}之前進(jìn)行調(diào)用，就可以得到如下的結(jié)果過(guò)：

0-1背包問(wèn)題答案截圖

最長(zhǎng)公共子序列

另一個(gè)經(jīng)常被當(dāng)做編程挑戰(zhàn)的問(wèn)題的動(dòng)態(tài)規(guī)劃問(wèn)題是最長(zhǎng)公共子序列(LCS)：找到兩個(gè)字符串序列的最長(zhǎng)子序列的長(zhǎng)度阶祭。最長(zhǎng)子序列是指筝野，在兩個(gè)字符串序列中以想聽的順序出現(xiàn)晌姚，但不要求連續(xù)(非字符串子串)的字符串序列。我們看一下下面的問(wèn)題描述：

最長(zhǎng)公共子序列的問(wèn)題描述

我們看一下算法的具體實(shí)現(xiàn)：

// 最長(zhǎng)公共子序列
lcs('acbacd', 'abcadf')
function lcs(wordx, wordy){
    let m = wordx.length;
    let n = wordy.length;
    let l = [];
    let solution = [];
    let i ,j, a, b;
    for( i = 0; i<= m; ++i ){
        l[i] = [];
        solution[i] = [];
        for(j = 0; j <= n ;++j ){
            l[i][j] = 0;
            solution[i][j] = '0';
        }
    }
    for(i = 0; i <= m; i++){
        for(j = 0; j <= n; j++){
            if(i == 0 || j== 0){
                l[i][j] = 0;
            }else if(wordx[i-1] === wordy[j-1]){
                l[i][j] = l[i - 1][j - 1] + 1;
                solution[i][j] = 'dialog'
            }else{
                a = l[i-1][j];
                b = l[i][j - 1];
                l[i][j] = (a > b) ? a : b;
                solution[i][j] = (l[i][j] == l[i-1][j]?'top':'left')
            }
        }
    }
    printSolution(solution,l,wordx,wordy,m,n);
    return l[m][n];
}
function printSolution (solution,l,wordx,wordy,m,n) {
    let a = m, b = n, i,j;
    let x = solution[a][b];
    let answer = '';
    while (x!== '0'){
        if (solution[a][b] === 'dialog') {
            answer = wordx[a-1]+ answer;
            a--;
            b--;
        }else if(solution[a][b] === 'left'){
            b--;
        }else if(solution[a][b] === 'top'){
            a--;
        }
        x = solution[a][b];
    }
    console.log('lcs:'+ answer);
}

結(jié)果的矩陣是：

l矩陣

solution的矩陣

矩陣鏈相乘

這個(gè)問(wèn)題的目的是找到一組矩陣相乘的最佳順序歇竟，讓我們可以更好的理解這個(gè)問(wèn)題挥唠，讓我們可以更好的理解這個(gè)問(wèn)題，n行m列的矩陣A和m行p列的矩陣B相乘焕议，結(jié)果n行p列的矩陣C宝磨。考慮我們想做A*B*C*D的乘法，因?yàn)槲覀兛梢宰屵@些矩陣以任意的順序相乘懊烤，因此我們考慮一下如下的情況：

• A是一個(gè)10行100列的矩陣
• B是一個(gè)100行5列的矩陣
• C是一個(gè)5行50列的矩陣
• D是一個(gè)50行1列的矩陣

在這個(gè)例子中，我們有5種相乘的方式：
(A(B(CD))):乘法運(yùn)算的次數(shù)是1750次
((AB)(CD)):乘法運(yùn)算的次數(shù)是5300次
(((AB)C)D):乘法運(yùn)算的次數(shù)是8000次
((A(BC))D):乘法運(yùn)算的次數(shù)是75500次
(A((BC)D):乘法運(yùn)算的次數(shù)是31000次
由此我們可以看到宽堆，相乘的順序不一樣腌紧，要進(jìn)行的乘法的原酸的總數(shù)也有很大的差異，那么畜隶，要如何構(gòu)建一個(gè)算法呢壁肋，來(lái)求出最少的乘法的運(yùn)算的操作次數(shù)？矩陣鏈相乘的算法如下：

function matrixChainOrder(p,n){
    let i,j,k,l,q,m=[];
    for(i = 1; i<=n; i++){
        m[i] = [];
        m[i][i] = 0;
    }
    for(l = 2; l < n; l++){
        for(i = 1; i<= n-l+1; i++){
            j = i + l - 1;
            m[i][j] = Number.MAX_SAFE_INTEGER;
            for(k = i; k <= j - 1;k++){
                // 用來(lái)計(jì)算給定括號(hào)順序的乘法運(yùn)算的次數(shù)籽慢，并將次數(shù)保存在輔助矩陣m中
                q = m[i][k] + m[k + 1][j] + p[i - 1]*p[k]*p[j]; 
                if(q < m[i][j]){
                    m[i][j] = q;
                }
            }
        }
    }
    return m[1][n-1];
}
let p = [10,100,5,50,1];
let len = p.length;
console.log(matrixChainOrder(p,len));