Many programmers simply don’t like recursion. The general idea of recursion is one of the more difficult topics to grasp. This is because our cognitive abilities are developed through experience, and the concept of recursion doesn’t occur very frequently in our everyday lives, but it is there if you look hard enough.
Think of when you were a kid and were amazed by what you could do with two mirrors and the right angle, creating infinite layers of reflection. That illustrates recursion quite well. Another good example of recursion in nature is fractals. The self repeating structure of fractals makes them a perfect example, many implementations of fractals make use of recursive functions.
Our everyday lives may not include too much recursion, but that all changes when you step over into the world of programming. This article will explain when its a good idea to use recursion, when its not such a good idea, and even provide a few examples. For many functions or procedures, you could implement them recursively or iteratively, its up to you to decide which method is most efficient.
For a simple example, we’ll write a function to compute the n’th element of the fibonacci sequence. This particular task proves to be horribly inefficient when using recursion, despite the seemingly simpler algorithm, but we’ll get to that in a second. For now, let’s take a look at the code for the recursive method (all code examples are in C++):
int fib_rec(int n) {
if(n<=1) return
1;
else return fib_rec(n-1) + fib_rec(n-2);
}
This is pretty straightforward, if n is less than or equal to 1 (the first element), 1 is returned. If not, the sum of the two previous elements is returned. Lets compare this to an iterative implementation with the same functionality. Here’s the code:
int fib_lin(int n) {
if(n<=1) return
1;
int last = 1;
int nexttolast = 1;
int answer = 1;
for(int i=2; i<=
n; i++) {
answer = last + nexttolast;
nexttolast = last;
last = answer;
}
return answer;
}
This does the same thing except holds the previous two elements in variables to avoid a recursive call.
If you were to compile and run these examples, you would find the recursive method to be very slow. Why is this? Its because for every call that is made, the function must be recursively called until n = 1. Suppose you call the function for n=7, it will then call itself for n=6 and n=5. Then n=6 will call for n=5 and n=4, and n=5 will call for n=4 and n=3, and so on. As you can see, this function will end up calculating each element several times (except for the last element). The number of operations for this function actually grows at the exact same rate as the fibonacci sequence itself, which is not good. To combat this problem, the iterative function above stores the previous two elements in variables, so they don’t have to be recalculated.
This example is one where recursion is definitely a bad idea. Now lets take a look at when recursion is very useful.
One of the most important parts of programming is the ability to sort and search data efficiently. This is the heart and soul of any application that manages large amounts of data. Many of the most efficient searching and sorting algorithms make use of recursion. For example, Mergesort is one of the best sorting algorithms. It has a very good worst-case run time of O(N log N). Here is an implementation of Mergesort:
void mergesort(int[]
a, int[] tempa, int
left, int right) {
if(left < right) {
int center = (left + right) / 2;
mergesort(a, tempa, left, center);
mergesort(a, tempa, center + 1, right);
merge(a, tempa, left, center + 1, right);
}
}
This is the driver for mergesort. How this algorithm works is it takes an array and splits it into subarrays. The variables ‘left’, ‘center’, and ‘right’ are the bounds of the subarrays. These bounds are passed as parameters in the recursive calls. The subarray information is then sent to a separate procedure called ‘merge’ which, as the name implies, merges the sorted subarrays into one sorted array.
This is an excellent example of the power of recursion when used correctly. Many other sorting algorithms also use recursion, including Quicksort, which is the fastest sorting procedure in practice.
Storing and searching data is also familiar ground for recursion. The Binary Search Tree (BST) is a very powerful data structure that is commonly used. You could implement a BST however you wish but recursion makes the process much more compact and efficient. Consider this example of a find routine for a BST using linked lists:
Node* BST::find(int x, Node* SomeNode) {
if(SomeNode == NULL) return
NULL;
else if(x < SomeNode->Data)
return find(x, SomeNode->LeftChild);
else if(x > SomeNode->Data)
return find(x, SomeNode->RightChild);
else return SomeNode; //
match was found
}
In this member function, a recursive call is made passing the next appropriate node on the tree until it finds the node containing the matching data, or until it is NULL, indicating the data was not present in the BST. This type of recursion is very useful and also easier to follow than its iterative counterpart. For each time the function is called, it will recursively call itself at most once. This makes it a bit easier to analyze. On functions such as the mergesort and fibonacci shown above, there are two recursive calls made in the same run. That makes it harder to follow, but it also is where the real power of recursion is. Anytime you have a complex recursive algorithm, you definitely need to sit down and carefully analyze it, asserting that it isn’t unnecessarily repeating operations and the base cases are clearly defined to avoid infinite loops.
Recursion is an excellent tool to have and despite popular opinion, it really isn’t that bad once you give it a chance. Its just important to know when recursion should be used and when it shouldn’t. So go forth, and recurse responsibly.
Murdok provides free highly informative newsletters for web developers, IT professionals and small business owners. We deliver 50 million email newsletters per month and have over 4,000,000 unique opt-in subscribers. From our extensive range of email newsletters we can provide you with a selection of newsletters that best meet your interests.
