我们知道树是递归数据结构,我们在编写树的过程中使用递归,例如BST的删除方法等。
递归的好处是,我们的程序变得非常小(例如中序遍历的代码只有4或5行),而不是非递归程序,虽然会很长,但从理解的角度来看,不像递归程序那么复杂。这就是为什么我讨厌递归,而我更喜欢编写非递归过程,并且我已经在二叉搜索树和 avl 树中做到了这一点。
现在请详细说明,与递归过程相比,更喜欢非递归过程是坏事还是好事。”
递归是一种与其他工具一样的工具。你不have使用所有可用的工具,但您至少应该理解它。
递归使某一类问题变得非常容易和优雅地解决,而你对它的“仇恨”充其量是不合理的。这只是一种不同的做事方式。
下面以递归和迭代形式显示了“规范”递归函数(阶乘),在我看来,递归形式更清楚地反映了f(1) = 1, f(n) = n*f(n-1) for n>1
.
Iterative: Recursive:
def fact(n): def fact(n):
r = n if n == 1:
while n > 1: return 1
r = r * n return n * fact(n-1)
n = n - 1
return r
差不多是only我更喜欢迭代解决方案而不是递归解决方案(对于真正适合递归的解决方案)是当堆栈大小的增长可能导致问题时(上面的阶乘函数很可能是其中之一,因为堆栈增长取决于n
但它也可以由编译器优化为迭代解决方案)。但这种堆栈溢出很少发生,因为:
- 大多数堆栈都可以根据需要进行配置。
- 递归(尤其是尾端递归,其中递归调用是函数中最后发生的事情)通常可以由智能编译器优化为迭代解决方案。
- Most algorithms I use in recursive situations (such as balanced trees and so on, as you mention) tend to be
O(logN)
and stack use doesn't grow that fast with increased data. For example, you can process a 16-way tree storing two billion entries with only seven levels of stack (167 =~ 2.6 billion).
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)