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