摘要：对于函数调用开销，可以利用尾递归来解决，不过目前的引擎并没有实现对尾递归的优化，所以最开始我以为递归没有理由比非递归更快。递归与堆栈非递归的算法使用一个堆栈来实现。
最近刷leetcode 79题 Word Search需要用到DFS算法，由于是刷leetcode，心想不能用递归，影响效率，于是利用stack完成。之后又利用递归（使用cache）实现了一次，结果竟然是递归的算法比非递归更快。
「低效」的递归对于递归，通常会有效率低下的映像，一般是因为2点：
重复计算
函数调用开销
对于重复计算，可以缓存计算结果来解决。
对于函数调用开销，可以利用「尾递归」来解决，不过目前的v8引擎并没有实现对尾递归的优化，所以最开始我以为递归没有理由比非递归更快。
递归与堆栈非递归的DFS算法使用一个「堆栈」来实现。而同样，函数调用也是利用「栈」来完成。
首先，Javascipt并没有原生的堆栈这个数据结构，通常是利用数组来实现，效率上应该会有所损失。
其次，系统堆栈快于手动堆栈是没有疑问的，而且系统堆栈使用的是寄存器，比内存要快很多。
最后，函数调用会有额外开销这个是没法避免的，但是当函数变量不多，递归层级不深的时候，这个开销带来的效率损失不能抵消系统堆栈带来的效率提升。
综合来看，在不爆栈的情况下，大部分Javascript代码里使用了缓存的递归在算法效率上高于非递归算法，并且递归算法的表现力是完全高于非递归的。很多时候，出于臆断进行的所谓优化，完全是负优化。
关于递归的随想之前在看SICP的时候，发现函数式编程没有循环，非函数式语言的循环操作都是利用「递归」的形式来完成的。而且所有的递归，都可以改成迭代的形式，避免了递归重复计算的缺点，也无需使用缓存来加速递归的计算，省下了缓存的开销，所以有句话叫做“所有循环都是尾递归”。
总结惯性思维不可取，实践检验真理
递归 !== 慢
以后图的遍历、树的遍历、巴拉巴拉其它情况，直接写递归，谁怼我说递归效率低，就让他来solo。（莫名的开心咋回事儿啊？）
以上关于为什么递归快的推理全是推断，但是DFS非递归慢于递归是事实（Javascript中）, 跪求大神给出准确解读。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/99130.html
摘要：一直以来没有对函数式编程有一个全面的学习和使用，或者说没有一个深刻的思考。是不是轻松了其实函数式编程主张的就是以抽象的方式创建函数。后面咱们在系统性的学习下函数式编程。 一直以来没有对函数式编程有一个全面的学习和使用，或者说没有一个深刻的思考。最近看到一些博客文章，突然觉得函数式编程还是蛮有意思的。看了些书和文章。这里记载下感悟和收获。 欢迎团队姜某人多多指点@姜少。 由于博客秉持着简...
摘要：于年在意大利北部帕维亚的监狱中死亡。的死亡促使了现代犯罪学的诞生。写道，犯罪分子生下来就是罪犯。最近的一个例子便是，上海交通大学和在年月传到上的论文使用脸部图像自动推断罪犯。 任何关心如何确保 AI 技术朝着有利于人类发展的人都是本文的读者1844 年，意大利南部一个小城镇举办了一场审判会，一个名叫 Giuseppe Villella 的劳工因涉嫌窃取了5 个里考塔（注释：意大利奶制品，类似...
阅读 3181·2021-09-22 15:05
阅读 2753·2019-08-30 15:56
阅读 1056·2019-08-29 17:09
阅读 795·2019-08-29 15:12
阅读 2079·2019-08-26 11:55
阅读 3046·2019-08-26 11:52
阅读 3373·2019-08-26 10:29
阅读 1376·2019-08-23 17:19
