Recursing Nightmares...

In my first shot at picking on various technical styles and implementation techniques I thought I would pick recursion. It's a method that is in almost everybody's toolkit and it is one that is both incredibly useful and can also be incredibly painful. To give us something to look at, we will look at this simple Python example

#class for the node. Have a left, a right and a value
class treeNode:
    def __init__(self, initialValue = ''):
        self.value = initialValue
        self.left = None
        self.right = None

    #simple function for preorder traversal. Prints
    #out the prefix notation of the tree
    def prefix(self):
        print self.value
        if self.left != None:
            self.left.prefix()
        if self.right != None:
            self.right.prefix()

    #simple function for postorder traversal. Prints
    #out the postfix notation for the tree
    def postfix(self):
        if self.left != None:
            self.left.postfix()
        if self.right != None:
            self.right.postfix()
        print self.value

    #simple function for in order traversal. Prints
    #out the infix notation for the tree
    def infix(self):
        if self.left != None:
            self.left.infix()
        print self.value
        if self.right != None:
            self.right.infix()

    #evaluates the binary tree, assuming the tree consists of binary math
    #operators and integer values
    def evaluate(self):
        if self.left != None and self.right != None and self.value == '+':
            return self.left.evaluate() + self.right.evaluate()
        if self.left != None and self.right != None and self.value == '-':
            return self.left.evaluate() - self.right.evaluate()
        if self.left != None and self.right != None and self.value == '*':
            return self.left.evaluate() * self.right.evaluate()
        if self.left != None and self.right != None and self.value == '/':
            return self.left.evaluate() / self.right.evaluate()
        if self.left == None and self.right == None:
            return int(self.value)
            

#create a tree that represents (3 * (14 + 15)). b acts as the root
a = treeNode('3')
b = treeNode('*')
c = treeNode('14')
d = treeNode('+')
e = treeNode('15')

b.left = a
b.right = d
d.left = c
d.right = e

root = b

#show the results
print "prefix"
root.prefix()
print "\npostfix"
root.postfix()
print "\ninfix"
root.infix()

print "\nanswer: " + str(root.evaluate())
			

The results of running this script are as follows

prefix
*
3
+
14
15


postfix
3
14
15
+
*


infix
3
*
14
+
15


answer: 87
			

The Good

What makes recursion so damn appealing to most people? The main reason is that it makes many programming problems that would be hard to code in an iterative manner much easier. Almost trivial in some cases. The easiest example to illustrate this is what everybody learns in their data structures class, binary tree traversal.

Looking at the above example, you can see that doing things like changing the order of the tree traversal is as simple as moving one line of code. In addition to that, the code is very compact and clean. The comments are almost unnecessary to tell you what is going on.

If you go onto more complex things like parsing grammars, you will see that there is a whole category of grammars based on whether they can be implemented in a recursive fashion. If you remember your compilers course, you will probably remember the various differences between top down and bottom up parsers, various types of context free grammars and what BNF means. Most of us have nightmares when trying to remember this stuff and are forced to occasionally review them.

The Bad

We have already seen that recursion is a very powerful construct that makes many coding tasks simple to describe in programming languages that support recursion. So what can be so bad about recursion? For one thing, it can be doggone slow. One of the first programs I ever learned in school that showed off the power of recursion, and I think just about everybody learns this one, is calculating fibonacci numbers. The example usually looks something like this

def fibr(n):
    if n < 2:
        return n
    else:
        return (fibr(n-1) + fibr(n-2))

This is very compact code. Runs beautifully for small numbers. You start getting somewhere up to around 30 and is takes a noticeable time to run in your python interpreter. Now you can of course implement this in a faster language, but the fact remains that when using a recursive algorithm things slow down. Every call to the function has to allocate a stack frame. You have a lot of intermediate results and function returns which are all computationally intensive. This isn't even a bad example of the sorts of things that can happen when you use recursive functions. We'll get to that later. Meanwhile, back in your class, chances are your professor (or your algorithms book, if you happen to have read it. You should.) didn't talk much about different implementations or the tradeoffs of different approaches. Maybe in your advanced data structures and algorithms class, possibly, but likely in the first class if the instructor got you to understand how to write recursive functions and the power they have, they'll have considered their job done. I wish when talking about recursion and fibonacci numbers they also included an example like this

def fiba(n):
    l=[0,1,1]
    if n > 2:
        for x in range(n-2):
            l.append(int(l[x+1]) + int(l[x + 2]))
    return l[n]

The above code looks slightly messier than the recursive implementation. It uses an array to calculate the values and stores them and returns the last element. This is MUCH more efficient than the recursive function, is the same number of lines and looks only slightly more complex with that extra level of nesting in there. Needless to say, if you are going to do something like calculate fibonacci numbers, you should use some looping construct vs. recursion, assuming that your language has looping constructs (some don't, although given the bent of this site, I'm not sure I expect many haskell programmers frequenting these pages). They are usually a good way to implement many recursive algorithms much more efficiently. Especially algorithms like the fibonacci number routine, which is tail recursive.

This is my first, last and only plead to all the computer science professors and lecturers out there to please find a more interesting problem than fibonacci numbers to demonstrate recursion. In addition to teaching your students bad habits, there are groups of people out there would dismiss one language over another simply because of how well it runs a recursive implementation of fibonacci numbers. It may be a good example to get the point across, but it ends up instilling a lot of long term bad habits.

The Ugly

Stack overflow. This is the bane of just about anybody that has written a non-trivial application using recursion to implement one or more of the algorithms. Even the big boys in Redmond have problems with recursion from time to time, and I'm guessing they have more testing resources and likely, on average, a more talented development staff than you or I do. When implementing an algorithm recursively, you better make sure that you really need every local variable that you use. You better make sure you have an exit condition so you don't infinitely recurse. In cases that can likely be large, like regular expressions you should think twice before using recursion to do the implementation.

When comes down to it, recursion can be just plain hard. The possibility of running infinitely, the slow down you are virtually guaranteed to get, needing to keep track of every last byte (how many people who program even like doing this sort of thing anymore) so as to minimize the possibility of a stack overflow and putting in various checks to exit early are all things you should consider before implementing an algorithm recursively. If you don't like thinking about these sorts of things, using recursion probably isn't for you, even if you do think "it's kind of neat".

So Really, How Do You Feel?

As with most tools that are extremely powerful and dangerous, know what you are doing, be careful, and take reasonable precautions. Recursion can be a great tool. Use it wisely. If you can find a way to not use recursion, chances are you will be much better off in the long run.