Recursion: Where Bunnies meet Trekkers.

What is recursion?

"To use recursion, or not to use recursion? That is the question."
Often, but not always, recursion is preferred over iteration. Before we choose to use recursion over iteration, the problem must be carefully examined, and the possible outcomes realized. Why doesn't this look like my presentation anymore? Simple. My presentation was based on one source, whereas all this information was found after wandering around on the Inet for a few hours. But, before we start...

Vocab! Weird and wacky, it helps to know these terms to understand what I'm talking about. And I don't mean useless blabberings... Click on the link above to either review or learn for the very first time, these weird words in English that actually mean something.

So, now that we've brushed up on some terms, let's continue. We know that it's a very powerful type of algorithm that is faster and more efficient, if applied to the right solution. For an easier understanding of what recursion may be like, let's take a look at one everyday application. Take a mirror, and hold it in front of another mirror. The results end up being that many images are produced, smaller and behind one another. This is similar to recursion in the sense that instead of making an image smaller, recursion breaks down problems into smaller chunks.

Take a very basic, everyday problem. You're flipping through a phonebook, looking for your friends' name. Since you know the alphabet, it's not hard to figure out relatively what section of the phone book it's in. Wouldn't it be faster if a computer could do your job? Keeping this scenario in the back of your mind, compare a sequential search to a binary search. A sequential search would take a few light years, in comparison to a binary search, which would only take a few minutes. Note that the recursive call in this algorithm is found at the bottom of the function, characteristic of a tail recursive function.

      Search(Dictionary, Word)

      if (Dictionary is one page in size)
          Scan the page for Word.
      else
      {
          Open dictionary to a point near the middle
          Determine which half of Dictionary contains Word.

          if (Word is in the first half of Dictionary)
              Search(First half of Dictionary, Word)
          else
              Search(Second half of Dictionary, Word)

      }

This is also an excellent example of the divide and conquer method; where you first divide the problem (or dictionary, in this case) and then conquer the appropriate half.

Bunny Rabbit Next, we'll look at rabbits. They are an excellent example of the Fibonacci sequence. Before we go any further, though, we have to make some assumptions:

Rabbits live forever
Sexual maturity is reached 2 months after birth
They are always born in male / female pairs.

The recursive solution for calculating a specific number of rabbits lie in these terms:

Rabbit(n)=Rabbit(n-1)+Rabbit(n-2)
There are two base cases to be considered: Rabbit(1) = 1, if N is either 1 or 2; or Rabbit(n-1)+Rabbit(n-2) if N > 2. Plugging in a few test values, we find that the results resemble that of a Fibonacci sequence. It is relatively easy to code:

        int Rabbit
        {
          if (N <= 2)
             return 1;
          else //N > 2, so N-1 > 0 and N-2 > 0
            return Rabbit(N-1)+ Rabbit(N-2); //the recursive call
        }

A box trace of this algorithm, however, proves that appearances can be decieving - it ends up being rather inefficient.

Spock's Dilemma... what to choose?
The mission: To go where no man has gone before. Time is running short, but a new galaxy, with N planets, has been found. What to do? He can only visit K planets. His eye has landed on a special planet that he must see. After a moment of thought, he figures out the following:

      C(n,k)=C(n-1, k-1)+C(n-1, k) or
      C(k, k) = 1 or
      C(n, 0) = 1 or
      C(n, k) = 0

Like the code for the Rabbit function, this one is also very simplistic to code, but very inefficient. The recursive calls are found at the bottom of the function, which is characteristic of tail recursion. Not always is there one base case that the recursive function breaks down into, there can be more than one, and in Spock's case, there are quite a few. Here, you can see two reasons why iteration may be a little more efficient, but more complicated to code. For a more detailed explaination, see the textbook Walls and Mirrors. Let's go on...

In conclusion, you must assess the situation before deciding whether or not to use recursion or iteration in your algorithm.

Looking for that computer definition? Check out Foldoc for the definition you seek.

This site is a licensed mirror of the original Recursion.
Confused? Need to brush up on your basics of C++? Return to the World of C++..