摘要：簡單算法之遞歸我向算法工程師請教如何學好算法，他跟我提議說先看懂漢諾塔，這是一個小朋友都會玩的游戲，里面用到了遞歸的思想。遞歸實現倒計時函數下面這個倒計時函數使用了遞歸，而且使用了尾遞歸優化。

別想太多，肯定要！！！

你以為的算法是各種排序，選擇排序、快速排序、歸并排序，廣深搜索、動態規劃......

然而，算法實際上指的是解決某個實際問題的方法。

解決同一個問題的方法有很多，比如循環輸出某個數組，可以有for、for in、for of、map、forEach等，不同的實現方法會反映不同的性能，這些性能通常用執行時間來表示，執行時間越短，性能越好，目前我可以告訴你的是，上面的幾個循環中，原生for循環的性能是最好的。

下面講的都是非常非常非常非常簡單的算法知識！！你千萬不要害怕！！

數組是算法中最常用到的數據結構，給你一串數組，你能很快的根據索引找到那個元素。

你或許知道時間復雜度O(n)，我們叫他大O表示法，這是大寫字母O，不是數字0，別搞錯了。通常大O表示的是算法的最差情況。

數組的大O很好理解，讀取的時候，最壞情況就是1次，因為數組是內存上連續的地址（計算機的知識），可以直接根據地址（索引）找到那個元素。

寫入的時候，如果是在數組的末尾push新的元素，那么前面已有的元素地址不需要改變，但是如果是在數組的頭部push新的元素，那么所有已有的元素的地址都要加1，即需要移動n個元素，所以大O是n。

刪除操作時，和插入一樣，最好的情況是刪除末尾的元素，復雜度就是1，最壞的情況是刪除第一個元素，所有剩下的元素都需要地址減1，即需要移動n次。

或許你會發現上面有點不對勁，在刪除的時候，不是移動 n-1 個元素嗎？其實這就是要知道的大O表示法只是描述次數和數據量的線性關系，我們關注的是線性變化的規律，不在乎那一點點影響。

鏈表比較復雜，我們這里只關心鏈表的一些特點。

鏈表和數組一樣，通常也存在內存中，鏈表可以存在內存的任何地方，它不一定是連續的。這句話你可能不太理解。舉個例子，假設你有的內存條有8G，這8G可能被分配給多個應用程序，你創建了一個數組，長度是10，那么，系統會分配10個連續的內存地址給你使用。而鏈表呢，假設你有10個數據，可以通過鏈表插入到內存的空余地址位置，中間可能被其他數據隔開。類似于插班生來到了你們班，插入了任意一個空位里面。

鏈表還有一個重要的特性就是他的讀取必須是從頭開始遍歷，因為只有當前的元素位置才有下一個元素的指針！！你不能直接讀取第N個元素！

你會發現鏈表的讀取大O是n，也就是說最壞的情況下，如果那個需要讀取的元素剛好在鏈表的最末尾，那么，你就需要遍歷整個鏈表。

寫入和刪除都是O(1)，這和鏈表的特點有關，你可以在任意一個指針寫入新的元素和刪除鏈表的元素，而只需要將前一個元素的指針指向新的元素或者下一個元素即可。鏈表沒有地址的概念，所以不需要移動地址。

上面的文字你覺得抽象的話，可以看下面的表格，假設這一段內存條，上面一共有8個內存地址，現在都是空余的，當你創建一個長度為2的數組時 new Array(2)，系統會分配2個內存地址給數組，可能是地址0，1。然后繼續創建一個長度為1的數組 new Array(1)，系統會分配1個內存地址給數組，假設是地址4，現在整個內存被2個數組給分割開來了，單個數組的內存一定是連續的，不同的數組之間不需要連續。

這時候，你再創建一個鏈表，有3個元素，現在地址2、3、5、6、7都是空閑的，假設鏈表的第一個元素是2，那么下一個元素可以指向任意一個空閑的地址，比如3，到地址3的時候，地址4已經有數組的元素在占用了，不用擔心，鏈表可以將指針指向地址5，這樣鏈表的第三個元素就存儲在地址5上面了。

這樣你是不是更加清晰的理解了數組和鏈表的基本特點了。

數組和鏈表也可以組合起來成為一種復合型的數據結構，稱為“鏈組結構”，不是戀父、不是戀母，而是鏈組！

作為前端，實際上只需要考慮和數組相關的基本算法就行了，還有就是各種性能提升的訣竅。

我向算法工程師請教如何學好算法，他跟我提議說先看懂漢諾塔，這是一個小朋友都會玩的游戲，里面用到了遞歸的思想。但是我在這里不說漢諾塔，而是從遞歸的簡單實現入手。

以前我也寫過遞歸的文章，ES6中也有尾遞歸優化的介紹。但遞歸的思想不只是應用在階乘算法中，還有各種場景需要遞歸，特別是在函數式編程中，遞歸的地位顯得越發的重要。

下面這個倒計時函數使用了遞歸，而且使用了尾遞歸優化。你或許不了解尾遞歸優化，我想你可以去看一下 尾遞歸優化特點

function countdown(i) {
  if (i <= 0) return
  console.log(i)
  setTimeout(() => {
    return countdown(i-1)
  }, 1000)
}
countdown(10)

階乘是什么？n!表示 1X2X3X...Xn

function t(i, s=1) {
  if (i <= 0) return s
  s *= i
  return t(i - 1, s)
}
const s = t(5)
console.log(s)

需求是這樣的，假設你有一個數字組成的數組，現在你需要寫一個函數求所有元素的和，比如[2, 4, 6]。

這里不單單是遞歸的思想，還有一種思想叫做分而治之，分而治之的思想分為2個步驟，一是找出基線條件。二是每次調用遞歸都離基線條件更近一步。

那么數組[2, 4, 6]的基線條件是什么呢？其實它就是一個臨界情況，比如當數組元素為空時[]，或者數組只剩一個元素時[2]。這個基線有什么作用呢？當遞歸達到基線時，就返回結果，不再遞歸。

下面的代碼實際上是根據這樣一個步驟去執行的，[2, 4] + 6 => [2] + 4 + 6 => 2 + 4 + 6，通過數組不斷的拆分和求和，直至數組達到基線條件，這時候將相加的和返回。

未尾遞歸優化

function add_1(arr, len=arr.length, sum=arr[len-1]) {
 if(len <= 1) return sum
 return sum + add_1(arr.slice(0, len - 1))
}

const r = add_1([2, 4, 6])
console.log(r) // 12

尾遞歸優化

function add_2(arr, len=arr.length, sum=arr[len-1]) {
 if(len <= 1) return sum
 len = arr.slice(0, len - 1).length
 sum += arr[len - 1]
 return add_2(arr.slice(0, len - 1), len, sum)
}

const p = add_2([2, 4, 6])
console.log(p) //12

學習算法是一個漫長的過程，第一次學網頁設計的時候，div都學習了大半年才搞懂什么玩意，后來CSS的學習時間更長，js的學習從開始到現在始終在進行著，正則的學習一開始也是很痛苦，最后，輪到了算法，只有像以前學習前端知識那樣堅持下去，才能學好算法！！