树的递归和非递归程序 [英] Recursive and non recursive procedures for trees

问题描述

因为我们知道这些树是递归的数据结构，我们用BST的删除方式写出树的过程的循环。


的优势的递归是，我们的过程变得非常小（例如，遍历遍历的代码只有4或5行），而不是非循序渐进的过程，这在很大程度上并不像复现过程那么复杂。这就是为什么我讨厌递归，我更喜欢写非循环过程，我已经在二进制serach树和avl树中完成了。

现在请详细说明，优先于递归程序的非递归过程是坏的或好的事情

as we know that the trees are recursive data structures, We use recurrsion in writing the procedures of tree like delete method of BST etc.
the advantage of recurrsion is, our procedures becomes very small (for example the code of inorder traversal is of only 4 or 5 lines) rather than a non recurrsive procedure which would be lengthy but not as complex as recurssive procedure in understanding perspective. that is why i hate recurrsion and i prefer to write non recurrsive procedure and i have done that in binary serach trees and avl trees.
Now please elaborate that, prefering non recursive procedures over recurrsive procedures is bad or good thing."

推荐答案

递归是一种像其他任何工具，你不要使用每个工具都可以使用，但你应该至少明白这一点。

Recursion is a tool like any other. You don't have to use every tool that's available but you should at least understand it.

递归使得一类问题非常容易和优雅地解决，你的仇恨是不合理的

Recursion makes a certain class of problems very easy and elegant to solve and your "hatred" of it is irrational at best. It's just a different way of doing things.

规范递归函数（factorial）以递归和迭代的形式显示，在我看来，递归形式更清楚地反映了n> 1 的 f（1）= 1，f（n）= n * f（n-1） p>



The "canonical" recursive function (factorial) is shown below in both recursive and iterative forms and, in my opinion, the recursive form more clearly reflects the mathematical definition of 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 ，但也可以通过迭代解决方案进行优化编译器）。但是这个堆栈溢出很少发生：

Pretty much the only place I would prefer an iterative solution to a recursive one (for solutions that are really well suited for recursion) is when the growth in stack size may lead to problems (the above factorial function may well be one of those since stack growth depends on n but it may also be optimised to an iterative solution by the compiler). But this stack overflow rarely happens since:

1. 大多数堆栈可以在必要时进行配置。


2. 递归（特别是尾随递归，其中递归调用是在函数中发生的最后一个事情）通常可以通过智能编译器来优化到迭代解。


3. 我在递归中使用的大多数算法情况（如平衡树等等，如你所说）往往是 O（logN），堆栈使用不会随着数据增加而增长。例如，您可以处理一个16路树，其中只存储了七个级别的堆栈（16 ⁷ =〜26亿）的20亿条目。

1. Most stacks can be configured where necessary.
2. Recursion (especially tail-end recursion where the recursive call is the last thing that happens in the function) can usually be optimised to an iterative solution by an intelligent compiler.
3. 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 (16⁷ =~ 2.6 billion).

这篇关于树的递归和非递归程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！