Geek Girl

I recently conducted an interview in which I asked the young woman who was just out of school to explain recursion. She answered correctly and explained it in the most obvious way (and what we are taught in school) using the example of Fibonacci numbers. This got me thinking about recursion and that I should have asked her to give me a real world example of when you would use recursion. Then I had trouble thinking of an example of when I had used recursion.

It’s true we don’t use recursion in everyday programming much, and are generally discouraged from doing so unless it really makes sense. You can have stack overflow issues if you are working with large trees, or are unsure of how deep the function calls will go. But there are some common and some uncommon but interesting things happening with recursion in the real world. Here are five that I could come up with. The code is in C#.

1. Sorting

While Most languages have a built in “sort” function that you can call these days, and it’s not necessary to write your own, sometimes it’s good to know how they work. You may even be asked to write a sort algorithm in an interview. Several of the popular algorithms for sorting use recursion.
Quicksort is an example of a sorting algorithm that splits a contiguous memory location in two, divided by an arbitrarily selected value called a pivot. All values less than the pivot go into the left partition, and all values more than the pivot go into the right partition. Then the sort recursively drills down into the partitions in the same way until the entire list is sorted.

The main recursive function for a quicksort looks something like this…

       static void Quicksort(char[] array, int left, int right)
       {
            int pivot = Partition(array, left, right);

            if (left < index - 1)
                Quicksort(array, left, pivot - 1);

            if (index < right)
                Quicksort(array, index, right);
        }

2. Tree Traversal/Searching

Pretty much anything that can be represented in a tree structure can be traversed (or built) using recursive functions. Let say we have a basic Tree class that defines a tree of integers…

class Tree<int>     {         public Tree<int> Left { get; set; }         public Tree<int> Right { get; set; }         public int Value { get; set; }     }

Left represents the left sub tree and Right representing the right sub tree. We could traverse the tree by recursively dipping further down into the tree’s left and right branches like this.

        static IEnumerable EnumerateTree(Tree tree)
        {
            if (tree == null) break;
            foreach (int i in EnumerateTree(tree.Left)) 
                return i;
            return tree.Value;
            foreach (int i in EnumerateTree(tree.Right))
                return i;
        }

3. Parsing Context-Free Grammars in Compilers

I’m not going to try to explain Context-Free Grammars here, you can Google it if you want more information, but basically it is a set of grammar rules, used to define a programming language. If you have ever written a compiler or taken a compiler class in school, you know that a compiler must parse every program to check for syntax errors and they sometimes use recursive functions to do so. There are non-recursive parsers, but we won’t get into that here.

Context-Free Grammars lend themselves well to recursion because they can be structured into Parse Trees. Parse Trees represent all of the syntactical paths a language can legally take for a given construct. Here is a generic parse tree for an assignment statement.

A recursive algorithm can be used to traverse the parse tree similar to the Tree Traversal algorithm in number 2.

4. Fractals and Cancer Prognosis

Fractals are all around us. They are naturally recursive patterns that are found everywhere in nature. Fractals are infinitely repeating patterns such as in a tree or a snowflake. Look closer and you still see the same pattern, no matter how close you look. Fractals can be built recursively.

You could write a computer program using recursion to build a drawing of a tree. But there are more practical uses of fractals in programming. Fractals occur in human biology. Fractals, and thus recursion, are being used to analyze tumors found in patients with various types of cancer. This article explains better than I can how cancer cells are believed to be more fractal in nature than normal human cells. More and more computers are being used to aid in cancer prognosis.

5. Cheating at “Words with Friends”

I never condone cheating, but you could potentially write an algorithm (using recursion) to find you all of the anagrams of the letters you possess, then match them up with real words using a dictionary web service to see which ones are actual words. The anagram algorithm might something like this, in which the starting prefix is “” and the word is all of the letters that you have.

        static void OutputAnagram(string prefix, string word)
        {
            if (word.Length <= 1)
            {
                Console.WriteLine(prefix + word);
            }
            else
            {
                for (int i = 0; i < word.Length; i++)
                {
                    string cur = word.Substring(i, 1);
                    string before = word.Substring(0, i);
                    string after = word.Substring(i + 1);
                    OutputAnagram(prefix + cur, before + after);
                }
            }
        }

This algorithm works in finding all combinations of the letters using ALL of the letters, but there are obviously a lot more. For example, for the letters of scta,this algorithm finds the combinations (scta, scat, stca, stac, sact, satc, csta, csat, ctsa, ctas, cast, cats, tsca, tsac, tcsa, tcas, tasc, tacs, asct, astc, acst, acts, atsc, atcs). But what about cat, sat, at? I’ll leave the rest of the code up to you.

In what ways do you use recursion?