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

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

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

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

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

下面講的都是非常非常非常非常簡(jiǎn)單的算法知識(shí)！！你千萬(wàn)不要害怕！！

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

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

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

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

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

或許你會(huì)發(fā)現(xiàn)上面有點(diǎn)不對(duì)勁，在刪除的時(shí)候，不是移動(dòng) n-1 個(gè)元素嗎？其實(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ù)的。這句話你可能不太理解。舉個(gè)例子，假設(shè)你有的內(nèi)存條有8G，這8G可能被分配給多個(gè)應(yīng)用程序，你創(chuàng)建了一個(gè)數(shù)組，長(zhǎng)度是10，那么，系統(tǒng)會(huì)分配10個(gè)連續(xù)的內(nèi)存地址給你使用。而鏈表呢，假設(shè)你有10個(gè)數(shù)據(jù)，可以通過(guò)鏈表插入到內(nèi)存的空余地址位置，中間可能被其他數(shù)據(jù)隔開。類似于插班生來(lái)到了你們班，插入了任意一個(gè)空位里面。

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

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

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

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

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

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

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

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

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

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

下面這個(gè)倒計(jì)時(shí)函數(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è)你有一個(gè)數(shù)字組成的數(shù)組，現(xiàn)在你需要寫一個(gè)函數(shù)求所有元素的和，比如[2, 4, 6]。

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

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

下面的代碼實(shí)際上是根據(jù)這樣一個(gè)步驟去執(zhí)行的，[2, 4] + 6 => [2] + 4 + 6 => 2 + 4 + 6，通過(guò)數(shù)組不斷的拆分和求和，直至數(shù)組達(dá)到基線條件，這時(shí)候?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í)算法是一個(gè)漫長(zhǎng)的過(guò)程，第一次學(xué)網(wǎng)頁(yè)設(shè)計(jì)的時(shí)候，div都學(xué)習(xí)了大半年才搞懂什么玩意，后來(lái)CSS的學(xué)習(xí)時(shí)間更長(zhǎng)，js的學(xué)習(xí)從開始到現(xiàn)在始終在進(jìn)行著，正則的學(xué)習(xí)一開始也是很痛苦，最后，輪到了算法，只有像以前學(xué)習(xí)前端知識(shí)那樣堅(jiān)持下去，才能學(xué)好算法?。?/p>