递归与迭代

Question

说到处recursion都使用for循环是否正确？如果递归通常较慢,那么将其用于循环迭代的技术原因是什么？

如果始终可以将递归转换为for循环,那么可以采用经验法则吗？

Answer 1

递归通常要慢得多,因为所有函数调用必须存储在堆栈中以允许返回调用函数.在许多情况下,必须分配和复制内存以实现范围隔离.

一些优化(如尾调用优化)使递归更快,但并不总是可行,并且未在所有语言中实现.

使用递归的主要原因是

• 在许多情况下,当它模仿我们解决问题的方法时,它更直观
• 一些像树一样的数据结构使用递归更容易探索(或者在任何情况下都需要堆栈)

当然,每个递归都可以建模为一种循环:这就是CPU最终要做的事情.递归本身更直接地意味着将函数调用和作用域放在堆栈中.但是将递归算法更改为循环算法可能需要大量工作并使代码不易维护:对于每个优化,只应在某些分析或证据表明有必要时尝试.

Answer 2

说使用for循环的所有递归都可以使用吗？

是的,因为大多数CPU中的递归都是用循环和堆栈数据结构建模的.

如果递归通常较慢,使用它的技术原因是什么？

它不是"通常较慢":它的递归被错误地应用得错误.最重要的是,现代编译器擅长将一些递归转换为循环而不需要询问.

如果始终可以将递归转换为for循环,那么可以采用经验法则吗？

为迭代解释时最佳理解的算法编写迭代程序; 为递归程序编写递归程序,最好以递归方式解释.

例如,通常以递归方式解释搜索二叉树,运行快速排序以及在许多编程语言中解析表达式.这些也是最好的递归编码.另一方面,计算因子和计算斐波纳契数在迭代方面更容易解释.使用递归对他们来说就像是用大锤乱打苍蝇:这不是一个好主意,即使大锤做了很好的工作吧⁺.

⁺我从Dijkstra的"编程学科"中借用了大锤的类比.

Answer 3

题 :

如果递归通常较慢,那么将其用于循环迭代的技术原因是什么？

答案:

因为在某些算法中很难迭代地解决它.尝试以递归和迭代方式解决深度优先搜索.你会发现用迭代解决DFS很难.

尝试的另一个好处是:尝试迭代地编写Merge排序.这需要你一段时间.

题 :

说使用for循环的所有递归都可以使用吗？

答案:

是.这个帖子对此有很好的答案.

题 :

如果始终可以将递归转换为for循环,那么可以采用经验法则吗？

答案:

相信我.尝试编写自己的版本以迭代地解决深度优先搜索.您会注意到一些问题更容易以递归方式解决.

提示:当你解决一个可以通过分而治之的技术解决的问题时,递归是很好的.