对于递归的傲慢与偏见

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

「低效」的递归

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

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

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

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

递归与堆栈

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

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

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

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

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

关于递归的随想

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

总结

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