图的dfs非递归算法性能效率如何？

Question

老师你好，我想请教一下，图的dfs非递归算法性能效率上与递归的dfs比如何呢？

Answer 1

liuyubobobo 2021-10-27 13:19:18

在大多数时候，非递归算法都比递归算法效率高。

但是，在现代计算机上（非嵌入式设备），尤其是算法面试问题（或者竞赛问题）的范围，如果没有极其特殊的数据，在大多数时候，都可以忽略递归带来的额外时间消耗。尤其是当书写一个递归算法远远比非递归算法容易的情况下。

继续加油！：）

• 提问者 陈圣 #1

  谢谢您的回答，所以我这样理解不知对不对，如果在生产环境下追求极致性能的速度和空间优化上，还是需要非递归实现的，用kernel系统的调用栈可能也会带来用户态和内核态转换的时间开销吧。

• liuyubobobo 回复 提问者 陈圣 #2

  对的。追求极致的性能应该避免递归。但我还是建议加一个条件：或者是底层开发；或者是使用编译型语言（底层开发通常使用的也是编译型语言，但底层开发更性能敏感。另：其实现在的编译器性能优化越来越好。很多简单的递归在编译阶段编译出来是非递归。）。应用层开发不一定。因为很多应用层的环境，解析器效率不高，如果开发者手动处理这种优化，甚至在一些特殊情况下，非递归反而效率低。（在应用层面，手动创建一个栈，手动分析状态，反而比直接用系统栈慢。因为前者每一条指令都需要解析，后者则直接调用系统底层机制。）
  
  如果真的这么性能敏感，应该具体问题具体分析，在你的开发平台上找最佳方式。
  
  这也是为什么，如果你去看 20 年前的教材，在讲到递归的时候，通常都会提到递归比非递归更消耗性能的问题，但是在现如今的教材上，已经很少强调这个问题。20年前基本上所有的编程都可以叫底层开发，并且没有那么多（近乎没有）解释型语言。

• 提问者 陈圣 #3

  谢谢您的解答，您让我想到了一个方法，我应该使用高精度的时间函数实际测试一下具体的算法时间，这样就可以知道编译器优化后非递归和递归之间的性能差异了。这一年来一直在看您的课程，学到了很多东西。

点开查看后面1条评论