摘要：這是一個(gè)簡單的遞歸函數(shù)，你可以使用它來生成數(shù)列中指定序號(hào)的數(shù)值這個(gè)函數(shù)的問題在于它的執(zhí)行效率非常低有太多值在遞歸調(diào)用中被重新計(jì)算。

本章內(nèi)容銜接上一章　數(shù)據(jù)結(jié)構(gòu)與算法：二分查找

兩種基本數(shù)據(jù)結(jié)構(gòu)：

數(shù)組

常見操作: 數(shù)組降維、數(shù)組去重

鏈表

遞歸：遞歸是很多算法都使用的一種編程方法

　　- 如何將問題分成基線條件和遞歸條件
　　- 分而治之策略解決棘手問題

棧

　- 調(diào)用棧(call stack)
　- 遞歸調(diào)用棧

常見排序算法：很多算法僅在數(shù)據(jù)經(jīng)過排序后才管用。如二分查找,它只能用于有序元素列表。

　- 冒泡排序
　- 選擇排序
　- 插入排序
　- 希爾排序
　- 歸并排序
　- 快速排序
　- 堆排序
　- 計(jì)數(shù)排序
　- 桶排序
　- 基數(shù)排序

需要將數(shù)據(jù)存儲(chǔ)到內(nèi)存時(shí),你請(qǐng)求計(jì)算機(jī)提供存儲(chǔ)空間,計(jì)算機(jī)給你一個(gè)存儲(chǔ)地址。需要存
儲(chǔ)多項(xiàng)數(shù)據(jù)時(shí),有兩種基本方式——數(shù)組和鏈表。但它們并非都適用于所有的情形,因此知道它
們的差別很重要

給出：let arr = [[1, 2, 3], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10, 0];
需求：降維、去重、排序
做法：Array.from(new Set(arr.flat(Infinity).sort((a, b) => a - b)))


解析如下：
0. arr.flat(Infinity)  //直接降維值一維數(shù)組。
1. sort     //排序就不說了。
2. new Set()  //達(dá)到去重效果
3. Array.from(上一步輸出的結(jié)果)  //將上一步結(jié)果轉(zhuǎn)換為數(shù)組

遞歸（recursion）：程序調(diào)用自身的編程技巧。

遞歸滿足2個(gè)條件：

有反復(fù)執(zhí)行的過程（調(diào)用自身）

有跳出反復(fù)執(zhí)行過程的條件（遞歸出口）

遞歸就是指在定義一個(gè)概念和過程時(shí)，又用到了本身。
哲學(xué)的將, 遞歸的妙用就在，如果一個(gè)過程中又包含自身，那么這個(gè)過程就可以無窮地展開，不會(huì)在有窮的步驟后停止。但是描述這個(gè)過程只需要有窮的指令。以有窮表現(xiàn)無窮。

在數(shù)學(xué)與計(jì)算機(jī)科學(xué)中，是指在函數(shù)的定義中使用函數(shù)自身的方法。遞歸一詞還較常用于描述以自相似方法重復(fù)事物的過程。例如，當(dāng)兩面鏡子相互之間近似平行時(shí)，鏡中嵌套的圖像是以無限遞歸的形式出現(xiàn)的。也可以理解為自我復(fù)制的過程。
另外多提一句，遞歸和lambda 演算是兩個(gè)與圖靈機(jī)等價(jià)的計(jì)算機(jī)理論模型，感興趣的讀者可以去進(jìn)一步研究，這里不贅述。

由于遞歸函數(shù)調(diào)用自己,編寫這樣的函數(shù)時(shí)很容易出錯(cuò),導(dǎo)致無限循環(huán)。

例:編寫這樣倒計(jì)時(shí)的函數(shù)。

5...4...3...2...1

為此,你可以用遞歸的方式編寫:

 const countdown = (i) => {
    console.log(i)
    // base case 基準(zhǔn)條件
    if (i <= 0){
      return null
    } 
    // 隱藏的else是　遞歸條件
    countdown(i-1)
    return null
  }

  countdown(5)

編寫遞歸函數(shù)時(shí),必須告訴它何時(shí)停止遞歸。正因?yàn)槿绱?每個(gè)遞歸函數(shù)都有兩部分:基線
條件(base case)和遞歸條件(recursive case)。遞歸條件指的是函數(shù)調(diào)用自己,而基線條件則
指的是函數(shù)不再調(diào)用自己,從而避免形成無限循環(huán)。

可以去掉基準(zhǔn)條件執(zhí)行下代碼：

  const countdown = (i) => {
    console.log(i)
    // base case 基準(zhǔn)條件
    // if (i <= 0){
    //   return null
    // } 
    // 隱藏的else是　遞歸條件
    countdown(i-1)
    return null
  }

  countdown(5)

因?yàn)闊o限循環(huán)導(dǎo)致Maximum call stack size exceeded error

n! = n (n-1) (n-2) ... 1(n>0)

// 階乘
const fact = (x) => {
  if(x === 1) {
    return 1
  }
  return x * fact(x - 1) 
}

console.log(fact(5))

斐波那契數(shù)列可以定義為以下序列：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

可以看到，該序列是由前兩項(xiàng)數(shù)值相加而成的。這個(gè)數(shù)列的歷史非常悠久，至少可以追溯 到公元700年。它以意大利數(shù)學(xué)家列奧納多·斐波那契（Leornardo Fibonacci）的名字命 名，斐波那契在1202年使用這個(gè)數(shù)列描述理想狀態(tài)下兔子的增長。

這是一個(gè)簡單的遞歸函數(shù)，你可以使用它來生成數(shù)列中指定序號(hào)的數(shù)值

這個(gè)函數(shù)的問題在于它的執(zhí)行效率非常低

有太多值在遞歸調(diào)用中被重新計(jì)算。如果編譯器可以將已經(jīng)計(jì)算的值記錄下來，函

數(shù)的執(zhí)行效率就不會(huì)如此差。我們可以使用動(dòng)態(tài)規(guī)劃的技巧來設(shè)計(jì)一個(gè)效率更高的算法。

動(dòng)態(tài)規(guī)劃的本質(zhì)其實(shí)就是兩點(diǎn)：

自底向上分解子問題

通過變量存儲(chǔ)已經(jīng)計(jì)算過的解

根據(jù)上面兩點(diǎn)，我們的斐波那契數(shù)列的動(dòng)態(tài)規(guī)劃思路:

斐波那契數(shù)列從 0 和 1 開始，那么這就是這個(gè)子問題的最底層

通過數(shù)組來存儲(chǔ)每一位所對(duì)應(yīng)的斐波那契數(shù)列的值

樹的最大深度：該題目來自 Leetcode，題目需要求出一顆二叉樹的最大深度

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
   if(!root) return 0
   return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1 
};

對(duì)于該遞歸函數(shù)可以這樣理解：一旦沒有找到節(jié)點(diǎn)就會(huì)返回 0，每彈出一次遞歸函數(shù)就會(huì)加一，樹有三層就會(huì)得到 3。
但是遞歸真的很慢

我們可以寫一個(gè)函數(shù) 用以遞歸的快速計(jì)算

// memoize 全局函數(shù)：用以階乘，斐波那契數(shù)組等遞歸調(diào)用的快速計(jì)算
// useage: const memoizeFibonacci = memoize(fibonacci); memoizeFibonacci(45)

export function memoize(fn) {
  const cache = {};
  return function () {
    const key = JSON.stringify(arguments);
    var value = cache[key];
    if (!value) {
      value = [fn.apply(this, arguments)]; // 放在一個(gè)數(shù)組中，方便應(yīng)對(duì)undefined，null等異常情況
      cache[key] = value;
    }
    return value[0];
  }
}

Stack Overflow上說的一句話:“如果使用循環(huán),程序的性能可能更高;如果使用遞歸,程序可能
更容易理解。如何選擇要看什么對(duì)你來說更重要。” Recursion or Iteration?

棧是一個(gè)線性結(jié)構(gòu)，在計(jì)算機(jī)中是一個(gè)相當(dāng)常見的數(shù)據(jù)結(jié)構(gòu)。

棧的特點(diǎn)是只能在某一端添加或刪除數(shù)據(jù)，遵循先進(jìn)后出的原則

每種數(shù)據(jù)結(jié)構(gòu)都可以用很多種方式來實(shí)現(xiàn)，其實(shí)可以把棧看成是數(shù)組的一個(gè)子集，所以這里使用數(shù)組來實(shí)現(xiàn)

arr = [2,3,6,5,33,7,23]

def bubbleSort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+i]:
                arr[j],arr[j + i] = arr[j + i], arr[j]
    return arr

print(bubbleSort(arr))

arr = [2,3,6,5,33,7,23]

def selectionSort(arr):
    for i in range(len(arr) - 1):
        # 記錄最小的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小數(shù)時(shí)， 將i 和最小數(shù)進(jìn)行交換
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

print(selectionSort(arr))

arr = [2,3,6,5,33,7,23]

def insertionSort(arr):
    for i in range(len(arr)):
        preIndex = i-1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex]
            preIndex-=1
        arr[preIndex+1] = current
    return arr

print(insertionSort(arr))

arr = [2,3,6,5,33,7,23]

def shellSort(arr):
    import math
    gap = 1
    while(gap < len(arr)/3):
        gap = gap*3 + 1
    while gap > 0:
        for i in range(gap, len(arr)):
            temp = arr[i]
            j = i - gap
            while j >= 0 and arr[j] >temp:
                arr[j+gap] = arr[j]
                j-=gap
            arr[j+gap] = temp
        gap = math.floor(gap/3)
    return arr

print(shellSort(arr))

下一篇文章 數(shù)據(jù)結(jié)構(gòu)與算法:二叉樹算法

JS-Sorting-Algorithm
javascript描述數(shù)據(jù)結(jié)構(gòu)與算法（改自imooc）
算法圖解
常見算法ｊｓ實(shí)現(xiàn)
javascript-algorithms
排序算法總結(jié)