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

別想太多，肯定要?。?！

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

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

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

下面講的都是非常非常非常非常簡單的算法知識?。∧闱f不要害怕??！

數(shù)組是算法中最常用到的數(shù)據(jù)結(jié)構(gòu)，給你一串?dāng)?shù)組，你能很快的根據(jù)索引找到那個元素。

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

數(shù)組的大O很好理解，讀取的時候，最壞情況就是1次，因?yàn)?strong>數(shù)組是內(nèi)存上連續(xù)的地址（計算機(jī)的知識），可以直接根據(jù)地址（索引）找到那個元素。

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

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

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

鏈表比較復(fù)雜，我們這里只關(guān)心鏈表的一些特點(diǎn)。

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

鏈表還有一個重要的特性就是他的讀取必須是從頭開始遍歷，因?yàn)橹挥挟?dāng)前的元素位置才有下一個元素的指針??！你不能直接讀取第N個元素！

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

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

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

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

這樣你是不是更加清晰的理解了數(shù)組和鏈表的基本特點(diǎn)了。

數(shù)組和鏈表也可以組合起來成為一種復(fù)合型的數(shù)據(jù)結(jié)構(gòu)，稱為“鏈組結(jié)構(gòu)”，不是戀父、不是戀母，而是鏈組！

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

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

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

下面這個倒計時函數(shù)使用了遞歸，而且使用了尾遞歸優(yōu)化。你或許不了解尾遞歸優(yōu)化，我想你可以去看一下 尾遞歸優(yōu)化特點(diǎn)

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)

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

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

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

下面的代碼實(shí)際上是根據(jù)這樣一個步驟去執(zhí)行的，[2, 4] + 6 => [2] + 4 + 6 => 2 + 4 + 6，通過數(shù)組不斷的拆分和求和，直至數(shù)組達(dá)到基線條件，這時候?qū)⑾嗉拥暮头祷亍?/p>

未尾遞歸優(yōu)化

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

尾遞歸優(yōu)化

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

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