树的递归和非递归过程

Question

因为我们知道树是递归数据结构,我们使用recurrsion来编写树的程序,如BST的删除方法等
.复发的优点是,我们的程序变得非常小(例如,遍历遍历的代码只有4或者是5行)而不是非复原程序,这种程序虽然冗长但不像理解透视中的递归程序那么复杂.这就是为什么我讨厌复发,我更喜欢写非复原程序,我已经在二元serach树和avl树做了.
现在请详细说明,更喜欢非递归程序而不是复发程序是不好或好事."

Answer 1

递归是一种与其他工具一样的工具.你不具备使用每一个工具这是可用的,但你至少应该了解它.

递归使得某类问题非常容易和优雅地解决,而你对它的"仇恨"充其量是不合理的.这只是一种不同的做事方式.

下面以递归和迭代的形式显示了"规范"递归函数(阶乘),并且在我看来,递归形式更清楚地反映了数学定义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

几乎我唯一喜欢迭代解决方案的地方(对于非常适合递归的解决方案)就是当堆栈大小的增长可能导致问题时(上面的阶乘函数可能是堆栈之后的那个)增长取决于n但它也可能被编译器优化为迭代解决方案).但是这个堆栈溢出很少发生,因为:

1. 大多数堆栈可以在必要时进行配置.
2. 递归(尤其是递归调用是函数中发生的最后事情的尾端递归)通常可以通过智能编译器优化为迭代解决方案.
3. 我在递归情况下使用的大多数算法(例如平衡树等,正如你所提到的)往往是O(logN)和堆栈使用不会随着数据增加而快速增长.例如,您可以处理一个存储20亿个条目的16路树,只有7个堆栈级别(16 ⁷ = ~26亿).