• Log In
• Register

One of the most fascinating aspects of computing is its foundation in discrete mathematics. Of particular interest is the idea of recursing through a set of data with a function until all of the data has been consumed and digested resulting in the predicted outcome. Recursive functions are interesting because they take an entire data set, do something to it, and then feed a portion of that data set to itself, thus recursing.

What Exactly is Recursion?

The easiest way to understand recursion is to see it in an example. A simple example would be a function called "half()." We'll say that half() takes a number and calls itself on half of the number recursively. If we give it 4, it will call itself on half of 4 until it gets to a predetermined end state. In this example, we'll say our end state is 1. So calling the function would result in something like this:

half(4)            
[initial function call]
half(half(2))      
[initial function calls "half" on 2 and waits]
half(half(half(1)))
[1, the end state, is reached]
half(half(1))      
["half" returns 1 since it is the end state]
half(1)            
[again, 1 is returned]
1                  
[the initial "half" function exits, returning 1]

As you can see, the function calls itself over and over again increasing the depth of the call with each half it takes. Once the end state 1 is achieved, the function exits returning 1 each time until it backs all of the way out of the recursive depth that it had achieved.

Obviously, this is a very simple and trivial example, but it hits on the key points of recursion nonetheless:1

1. You have to have a function that calls itself with a smaller subset of the values with which it began.

2. The function must be aware that an end state exists which terminates the recursive process.

The Importance of Recursion

Recursion is important because it is how computers tend to get things done. Even though you can't see it, your computer is constantly relying on recursion to accomplish even the simplest tasks. As we saw with our simple example above, every time we recurse, we increase the depth of the function. In the realm of computers, this depth equates to memory and processor time. A poorly designed recursive algorithm can quickly use up system resources, leaving other processes starving for resources.

Have you ever had your computer go really slow in the middle of a calculation or process? Perhaps you were sorting a large number of files, or doing a huge calculation in a spreadsheet. No matter what you were doing, there is a good chance that the slow down you encountered was a result of non-optimal programming. Somewhere in the bowels of your computer, a function was probably asking for more and more memory and processor time in order to complete a task. As a result, your whole system suffered.

There are several ways poor programming could lead to a slowdown. This article will only consider the instance that deals with recursion. As we stated earlier, a recursive function calls itself on a subset of the initial data it was given. In addition to calling itself on a portion of the given data set, a recursive function can also do any number of other calculations. In our simple example, the implied calculation was "divide by 2." We must keep in mind that aside from recursing on data subsets, other calculations in a function also use up computer resources.

Measuring the Resources a Function Consumes

In computer science, there is something known as Big-O (pronounced "Big Oh") analysis. This analysis will tell you how resources a function will consume in relation to the size of the data set it is given and the operations it performs. It is usually given in terms of "n" where n is the number of elements in the data set. By definition, the term inside the Big-O parenthesis is a function that sets an upper-limit on the growth of the function in question as n increases, after some constant number of terms have been processed.2 For example, O(n) would be "Big-O of n," which means for n elements in a data set, n operations will be required to reach an end state. O(1) would mean that the function completes at a constant rate, regardless of n. O(n^2) is a general upper-limit on what you want to see in a function. Once you go beyond a number of operations equal to the square of the elements in the data set, you tend to start seeing poor performance, especially when using large data sets.

Analyzing a Function

So naturally, the question arrises: How can I look at a recursive function and tell how long it will run, AKA its Big-O analysis? This is where the elegance of mathematics can be applied to come to an easy solution. There are various ways to solve recursive problems, but we'll focus on my personal favorite: the iterative method.3

Step 1: Define Your Recurrence

The first thing we need to do before we can begin any sort of analysis, is define the recurrence that we want to consider. A recurrence defines an equation (or inequality) that describes a function in terms of itself with smaller input values. For example, let's say that we've written some function that, on each call to itself, must perform an operation on all of the data elements in the set given, and then call itself four times on half of that data set (see figure 1).

Step 2: Iterate the Recurring Piece

Simple expansion, or iteration, of the recurring portion would yield the results shown in figure 2.

Note that even though we've completed three iterations, the recurring function is still present. We can iterate forever and the term will still exist. Hopefully by now you see that doing so will be neither helpful nor necessary. The reason is that now that we've completed three iterations, we can see an obvious pattern. For each iteration, the last n-term is going to be multiplied by two raised to a power equal to the number of the iteration. Figure 3 shows this pattern using i to represent the number of the last iteration.

Step 3: Simplify with a Summation Expression

Now that we've got T(n) in terms of i, the number of iterations, we can simplify things by showing T(n) as a summation.

If it's not already obvious, you should note that we still have one major hole to fill before we can continue our analysis. We need to replace the question mark in figure 4 with the last iteration of our summation. So, how do we figure this out? Well, let's refer to figure 1 where we show our recurrence's end state being achieved when n is equal to 1. Since our recurrence is constantly dividing n by two, we can say that our last iteration will occur when n divided by some power of two (that we'll call 'a') is equal to 1. Knowing this, all we have to do is solve for a (see figure 5).

We're close to having our term for our last iteration. All we have to do now is subtract 1 because the last 1 is defined by the recurrence and should not be a part of the summation. Rather, it will be added to the result of the summation (see figure 6).

Step 4: Restate the Summation as an Equation in Terms of n

Now here's where a little knowledge of mathematical properties will go a long way. Right about now you're thinking that we've got a mess on our hands, but fear not! Using the formula that is shown in figure 7, we can simplify our equation to that shown in figure 8.

At this point the remaining math becomes intuitively obvious. We know that 2 raised to the power of lg n is equal to n raised to the power of lg 2. Since lg 2 is 1, this whole term simplifies to n. Since we're looking for our biggest term to determine our Big-O, our job is done. n-squared is obviously the largest term (see figure 9) therefore this recurrence is O(n^2).

Conclusion

And that's all there is to it. If this recurrence actually described an algorithm we were considering, we'd know that for every n elements we give it, it would have to perform n-squared operations. We could then use that information to determine if our algorithm is good enough to do what we need it to do. If not, then it'd be back to the ol' drawing board to come up with a new function and its analysis until we got one that met our standards.

Keep in mind, this is only one way to do this sort of analysis. There is more than one way to skin this cat. This one just happens to be my favorite. For more information, go to your local university and enroll in their 4-year computer science program. :-)

Discuss this Article

Have an opinion, a question, or correction? Leave comments for this article in the discussion area.