Recursive and non recursive procedures for trees

Question

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."

Answer 1

Recursion is a tool. Sometimes using the "tool of recursion" makes the code easier to read, although not necessarily easier to comprehend.

In general, recursive solutions tend to be good candidates where a "divide and conquer" approach to solving a specific problem is natural.

Typically, recursion is a good fit where you can look at a problem and say "aha, if I knew the answer for a simpler variant f this problem, I could use that solution to generate the answer I want" and "the simplest possible problem is P and its solution is S". Then, the code to solve the problem as a whole boils down to looking at the in-data, simplifying it, recursively generate a (simpler) answer and then go from the simpler answer to the answer as a whole.

If we consider the problem of counting the levels of a tree, the answer is that the height of the tree is 1 more than the height of the "tallest/deepest" of the children and the height of a leaf is 1. Something like the following code. The problem can be solved iteratively, but you'd, essentially, re-implement the call stack in your own data structures.

def tree_height (tree):
  if tree.is_leaf():
    return 1

  childmax = 0;
  for child in tree.children():
    childmax=max(childmax, tree_height(child))

  return childmax+1

It's also worth considering that Tail Call Optimization can make some recursive functions running in constant stack space.

Answer 2

Recursion is elegant, but prone to stack overflowing. Use tail-end recursion whenever possible to give the compiler the chance to convert it an iterative solution.

It's definitely you decision which tool you want to use - but keep in mind that most algorithms dealing with tree-like data structures are usually implemented recursively. As it's common practice, your code is easier to read and less surprising for others.

Answer 3

You should read about Tail Recursion. In general, if a compiler manages to apply tail recursion to a procedure, it it quite effective, if not, then not so.

Also a important issue is the maximum recusion depth of your compiler -- usually it's limited by the stack size. The downside here is that there's no graceful way to handle a stack overflow.

Answer 4

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.

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

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. 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).