資訊專欄INFORMATION COLUMN
摘要：對于函數(shù)調(diào)用開銷，可以利用尾遞歸來解決，不過目前的引擎并沒有實(shí)現(xiàn)對尾遞歸的優(yōu)化，所以最開始我以為遞歸沒有理由比非遞歸更快。遞歸與堆棧非遞歸的算法使用一個(gè)堆棧來實(shí)現(xiàn)。
最近刷leetcode 79題 Word Search需要用到DFS算法，由于是刷leetcode，心想不能用遞歸，影響效率，于是利用stack完成。之后又利用遞歸（使用cache）實(shí)現(xiàn)了一次，結(jié)果竟然是遞歸的算法比非遞歸更快。
「低效」的遞歸對于遞歸，通常會(huì)有效率低下的映像，一般是因?yàn)?點(diǎn)：
重復(fù)計(jì)算
函數(shù)調(diào)用開銷
對于重復(fù)計(jì)算，可以緩存計(jì)算結(jié)果來解決。
對于函數(shù)調(diào)用開銷，可以利用「尾遞歸」來解決，不過目前的v8引擎并沒有實(shí)現(xiàn)對尾遞歸的優(yōu)化，所以最開始我以為遞歸沒有理由比非遞歸更快。
遞歸與堆棧非遞歸的DFS算法使用一個(gè)「堆棧」來實(shí)現(xiàn)。而同樣，函數(shù)調(diào)用也是利用「?！箒硗瓿?。
首先，Javascipt并沒有原生的堆棧這個(gè)數(shù)據(jù)結(jié)構(gòu)，通常是利用數(shù)組來實(shí)現(xiàn)，效率上應(yīng)該會(huì)有所損失。
其次，系統(tǒng)堆?？煊谑謩?dòng)堆棧是沒有疑問的，而且系統(tǒng)堆棧使用的是寄存器，比內(nèi)存要快很多。
最后，函數(shù)調(diào)用會(huì)有額外開銷這個(gè)是沒法避免的，但是當(dāng)函數(shù)變量不多，遞歸層級不深的時(shí)候，這個(gè)開銷帶來的效率損失不能抵消系統(tǒng)堆棧帶來的效率提升。
綜合來看，在不爆棧的情況下，大部分Javascript代碼里使用了緩存的遞歸在算法效率上高于非遞歸算法，并且遞歸算法的表現(xiàn)力是完全高于非遞歸的。很多時(shí)候，出于臆斷進(jìn)行的所謂優(yōu)化，完全是負(fù)優(yōu)化。
關(guān)于遞歸的隨想之前在看SICP的時(shí)候，發(fā)現(xiàn)函數(shù)式編程沒有循環(huán)，非函數(shù)式語言的循環(huán)操作都是利用「遞歸」的形式來完成的。而且所有的遞歸，都可以改成迭代的形式，避免了遞歸重復(fù)計(jì)算的缺點(diǎn)，也無需使用緩存來加速遞歸的計(jì)算，省下了緩存的開銷，所以有句話叫做“所有循環(huán)都是尾遞歸”。
總結(jié)慣性思維不可取，實(shí)踐檢驗(yàn)真理
遞歸 !== 慢
以后圖的遍歷、樹的遍歷、巴拉巴拉其它情況，直接寫遞歸，誰懟我說遞歸效率低，就讓他來solo。（莫名的開心咋回事兒啊？）
以上關(guān)于為什么遞歸快的推理全是推斷，但是DFS非遞歸慢于遞歸是事實(shí)（Javascript中）, 跪求大神給出準(zhǔn)確解讀。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/99130.html
摘要：一直以來沒有對函數(shù)式編程有一個(gè)全面的學(xué)習(xí)和使用，或者說沒有一個(gè)深刻的思考。是不是輕松了其實(shí)函數(shù)式編程主張的就是以抽象的方式創(chuàng)建函數(shù)。后面咱們在系統(tǒng)性的學(xué)習(xí)下函數(shù)式編程。 一直以來沒有對函數(shù)式編程有一個(gè)全面的學(xué)習(xí)和使用，或者說沒有一個(gè)深刻的思考。最近看到一些博客文章，突然覺得函數(shù)式編程還是蠻有意思的。看了些書和文章。這里記載下感悟和收獲。 歡迎團(tuán)隊(duì)姜某人多多指點(diǎn)@姜少。 由于博客秉持著簡...
摘要：于年在意大利北部帕維亞的監(jiān)獄中死亡。的死亡促使了現(xiàn)代犯罪學(xué)的誕生。寫道，犯罪分子生下來就是罪犯。最近的一個(gè)例子便是，上海交通大學(xué)和在年月傳到上的論文使用臉部圖像自動(dòng)推斷罪犯。 任何關(guān)心如何確保 AI 技術(shù)朝著有利于人類發(fā)展的人都是本文的讀者1844 年，意大利南部一個(gè)小城鎮(zhèn)舉辦了一場審判會(huì)，一個(gè)名叫 Giuseppe Villella 的勞工因涉嫌竊取了5 個(gè)里考塔（注釋：意大利奶制品，類似...
閱讀 3301·2021-09-22 15:05
閱讀 2854·2019-08-30 15:56
閱讀 1123·2019-08-29 17:09
閱讀 865·2019-08-29 15:12
閱讀 2142·2019-08-26 11:55
閱讀 3226·2019-08-26 11:52
閱讀 3435·2019-08-26 10:29
閱讀 1428·2019-08-23 17:19
