对于递归的傲慢与偏见

最近刷leetcode 79题 Word Search需要用到DFS算法，由于是刷leetcode，心想不能用递归，影响效率，于是利用stack完成。之后又利用递归（使用cache）实现了一次，结果竟然是递归的算法比非递归更快。

「低效」的递归

对于递归，通常会有效率低下的映像，一般是因为2点：

• 重复计算
• 函数调用开销

对于重复计算，可以缓存计算结果来解决。

对于函数调用开销，可以利用「尾递归」来解决，不过目前的v8引擎并没有实现对尾递归的优化，所以最开始我以为递归没有理由比非递归更快。

递归与堆栈

非递归的DFS算法使用一个「堆栈」来实现。而同样，函数调用也是利用「栈」来完成。

首先，Javascipt并没有原生的堆栈这个数据结构，通常是利用数组来实现，效率上应该会有所损失。

其次，系统堆栈快于手动堆栈是没有疑问的，而且系统堆栈使用的是寄存器，比内存要快很多。

最后，函数调用会有额外开销这个是没法避免的，但是当函数变量不多，递归层级不深的时候，这个开销带来的效率损失不能抵消系统堆栈带来的效率提升。

综合来看，在不爆栈的情况下，大部分Javascript代码里使用了缓存的递归在算法效率上高于非递归算法，并且递归算法的表现力是完全高于非递归的。很多时候，出于臆断进行的所谓优化，完全是负优化。

关于递归的随想

之前在看SICP的时候，发现函数式编程没有循环，非函数式语言的循环操作都是利用「递归」的形式来完成的。而且所有的递归，都可以改成迭代的形式，避免了递归重复计算的缺点，也无需使用缓存来加速递归的计算，省下了缓存的开销，所以有句话叫做“所有循环都是尾递归”。

总结

• 惯性思维不可取，实践检验真理
• 递归 !== 慢
• 以后图的遍历、树的遍历、巴拉巴拉其它情况，直接写递归，谁怼我说递归效率低，就让他来solo。（莫名的开心咋回事儿啊？）
• 以上关于为什么递归快的推理全是推断，但是DFS非递归慢于递归是事实（Javascript中）, 跪求大神给出准确解读。