如果使用循环控制结构可以完成相同的任务,为什么要使用递归？

Question

当我开始学习递归时,不同的问题正在我脑海中浮现.递归为堆栈使用更多内存,并且由于维护堆栈通常会更慢.

如果我仍然可以使用for循环,使用递归有什么好处？我们描述了在条件为真之前反复重复的操作,并且我们可以使用递归或for循环.

为什么我会选择递归版本而我有更快的控制结构作为选项？

Answer 1

递归为堆栈使用更多内存,并且由于维护堆栈通常会更慢

这种说法远非普遍存在.它适用于您不需要将状态保存超过固定数量级别的情况,但这不包括许多可以递归解决的重要任务.例如,如果要在图形上实现深度优先搜索,则需要创建自己的数据结构来存储否则将进入堆栈的状态.

如果我仍然可以使用for循环,使用Recursion有什么好处？

将递归算法应用于通过递归最佳理解的任务(例如处理递归定义的结构)时,可以更清晰.在这种情况下,循环本身已不再足够:您需要一个数据结构来与循环一起使用.

为什么我会选择递归版本而我有更快的控制结构？

当您可以使用易于理解的更快的控制结构实现相同的算法时,您不一定会选择递归.但是,在某些情况下,您可能希望编写递归来提高可读性,即使您知道可以使用循环对算法进行编码,而不需要其他数据结构.现代编译器可以检测这种情况,并"重写"场景后面的递归代码,使其使用迭代.这使您可以充分利用这两个方面 - 一个符合读者期望的递归程序,以及不会浪费堆栈空间的迭代实现.

不幸的是,演示递归给你带来明显优势的情况的例子需要高级主题的知识,因此许多教育工作者通过使用错误的例子(例如阶乘和斐波纳契数)证明递归来获取快捷方式.一个相对简单的示例是为带括号的表达式实现解析器.你可以用许多不同的方式来做,有或没有递归,但是解析表达式的递归方式为你提供了一个易于理解的非常简洁的解决方案.