Contents  Introduction  Recursion  Introduction to Trees  General Trees  Adding, Removing  and Processing  Nodes  Conclusion  Source code  Printable version  Discuss this article  in the forums The Series  Introduction  Binary Trees

Recursion

Trees are highly recursive structures. I'm hoping that you will be somewhat familiar with recursion as a theory, because it is a difficult subject to get correct for most beginning programmers. Here is a tiny introduction to recursion (you'll probably want to find a more in depth tutorial if you've never heard the term before).

What is recursion? An old programmers joke has the definition of Recursion in the dictionary as this:

re·cur·sion n.: See Recursion.

The basic idea behind a recursive function is one which calls itself repeatedly on many different levels. A recursive structure, such as a tree, has itself as its own children, and is thus considered recursive. Recursion helps software engineers solve problems by dividing up complex problems into smaller sub-problems, and is often a great boost in algorithm completion time, because recursion helps to "divide and conquer" the problem at hand, thus reducing the complexity. I will go into this further in the next tutorial dealing with binary tree’s.

The basic recursive function will have two portions: the recursive part, and the terminating part. It is very important that recursive functions have a terminating part, because without it, the recursive function would never end. The above joke is an example of recursion without a terminating condition. If it were in a program, the program would continuously look up the definition of recursion forever.

Of course, having a machine run into infinite recursion is just as deadly as an infinite loop, but the difference between the two is that infinite recursion will eventually cause the machine or thread to quit out. This is because each recursive call allocates more information on the stack every time it is called, and when the machine or thread runs out of stack space, it quits out.

The stack is the most important part of recursion. It is an easy way to have the machine store current state information about a function, change to another object, and then return at a later time. Let's look at a simple recursion example:

int getPower( int number, int power )
{
  if( power != 1 )
    return number * getPower( number, power - 1 );
  else
    return number;
}

Here is the non-recursive solution to the same problem:

int getPower( int number, int power )
{
  int result = number;
  while( power > 1 )
  {
    result *= number;
    power--;
  }
  return result;
}

While the recursive example looks ugly and stupid, and the iterative example is far more efficient, it demonstrates an important idea behind recursion. The terminating case is where power is 1. When power reaches 1, it returns a number instead of calling itself again. The recursive portion of the function decides to let the function handle the power one less than the current power, as long as the current power is not 1. So if the function were to calculate 2 to the Nth power, it would first check to see if N was one, and if it isn't, it asks for the solution to the problem of 2^(N-1), until it gets to 2^1, in which case it returns 2. If N were 2, it would ask for 2^1 and multiply that by 2, and return. If N were 3, it would ask for the solution to 2^2 and muliply that by 2. That is the basis of recursion.

So why use it? If analyzed, the recursive getPower function is slower and harder to understand than the non-recursive iterative solution, so it quite obviously offers no advantage. Recursion is not used to its full potential in this example simply because I wanted to show you how a problem can be broken down into a smaller problem by using recursion (Look for tutorials on The Towers of Hanoi problem for a really cool demonstration of this effect).

The real reason we would use recursion is for a simple way of storing values on a 'path' for future use. Recursion store's the state of the algorithm at each level and allows the user to come back to that exact state later on. We will see this in use when using the tree traversal routines.

Next : Introduction to Trees