4年前 (2020-10-10)  Java系列 |   抢沙发  799 
文章评分 1 次,平均分 3.0
  1. 递归在某些算法中更难理解。一个可以自然地迭代表达的算法,如果递归地表达,可能就不那么容易理解了。
  2. 没有可移植的方法来判断深度递归可以在多大程度上不引起麻烦(机器有多少“堆栈空间”),也没有办法从太深的递归中恢复(“堆栈溢出”)。
  3. 你不能递归地做一些好事。例如,如果我要遍历一个二叉树,我可能想用For循环来完成:
tree t;
item *i;

for (i = first (t); i != NULL; i = next (i)) {
    ...do something with i...
}

但是如果您想这样做,就不能递归地编写遍历。将遍历分解为迭代或强制使用回调函数是唯一的两个选择。前者是两个缺点中较小的一个,因为你只需要做一次,然后就可以在遍历中使用多次。

4. 假设您需要向递归进程传递一些数据。您可能需要对访问的节点数进行计数,或者使用一组参数来确定在每个节点上要执行的操作,或者其他任何操作。为此,必须向每个递归调用传递一些数据。这是浪费时间和空间,除非你的编译器比我的编译器聪明得多。或者,您可以使用全局变量,但这并不是一个更好的解决方案。

现在,如果您要使用迭代解决方案,您可以只拥有一组局部变量,并且不需要递归地传递任何内容。这节省了在递归调用中传递这些内容所需的时间和内存。

5. 中途中止递归过程是一件痛苦的事。假设您正在使用一个函数来枚举二叉搜索树中的所有项,并且您在中途发现不需要再查看任何项。或者,考虑通过递归下降解析表达式时语法错误后中止的问题。尝试中止进程涉及到当前正在执行的实例与它所在的所有实例的协作。这是缓慢的,有时是恶劣的。setjmp()longjmp()的使用是一种替代方法,但与goto一样,在实际操作中最好避免使用这些构造。

更糟糕的是,假设在二叉搜索树的例子中,你在中途发现你需要改变方向,向后移动。我甚至不想去想如何递归地去做。这根本不切实际。

6. 避免递归调用通常可以避免其他类型的开销,例如系统不可避免的函数调用开销。在某些系统上,这可能很重要,因此从递归到迭代的转换可以提高速度和空间需求。

避免迭代也是有原因的:

迭代在某些算法中更难理解(见上文)。一个可以自然地递归表达的算法,如果迭代地表达,可能就不那么容易理解了。将递归算法转换为迭代算法也很困难,验证这些算法是否等效也很困难。

递归允许您在每次函数调用时分配额外的自动对象。迭代的替代方法是重复地动态地分配或调整内存块的大小。在许多平台上,自动分配要快得多,以至于它的速度加成超过了递归调用的速度损失和存储成本。(但正如上文所述,有些平台不支持大量自动数据的分配;这是一种取舍。)

所以具体要使用递归还是迭代解决问题,需要结合具体的业务场景并参考这些建议作出权衡。

 

除特别注明外,本站所有文章均为老K的Java博客原创,转载请注明出处来自https://javakk.com/584.html

关于

发表评论

表情 格式

暂无评论

登录

忘记密码 ?

切换登录

注册