In some computer science or software engineering degree programs functional programming plays a very minor role. There may be an elective course, or there may just be a short segment on recursion in CS101. I went through an introductory sequence that was taught in Java, which doesn’t lend itself to recursion. Probably as a direct consequence of the limitations of Java, recursion was only briefly covered as some kind of novelty concept in programming, and some students were quick to dismiss recursion as “useless” or “academic”.

If recursion gets only treated on a surface level it does look like little more than a novelty concept of little use, with the added disadvantage that it “makes code more difficult to understand.” Sure, the unfamiliar is often difficult to grasp, but the elegance of recursive functions should be self-evident. If you think about it, loops are much less natural. Instead of taking one step after another, you first measure how many steps you are going to take and then process data, and hope that the number of steps you initially determined is equal to the number of steps that is required for the data. This is why there are off-by-one errors in iterative programs but not in functional ones.

Many freshmen have a hard enough time understanding loops. Eventually they will view them as reliable, possibly because they don’t notice half their off-by-one errors, i.e. those that don’t throw an exception due to an out-of-bounds error. I think if you taught people functional programming first and only afterwards introduced them to Java or C++, they might view it as a step back. On the other hand, if you let them experience with recursion in a language that is not suited for it, they learn that it’s easy to blow up the stack, which leads to the formation of beliefs like the two following, which mere made by top posters on Stack Overflow. The context was that one guy posted about an issue he was having with Ruby, a multi-paradigm programming language that is hardly ideal if you want to program in a functional style because it can’t handle deep recursive calls well.

If you’re intentionally recusing 10,000 times, you’re doing it horribly wrong and abusing recursion.

In general, unbounded recursion is bad. Most recursion can be rewritten to be iterative.

The cause of the problem, though, was that Ruby is missing tail call elimination. Recursion itself is not the problem. A programming language with support for tail call elimination should handle recursion just fine. Both statements are therefore misguided. I’ve found that it’s not that uncommon that supposedly good programmers, but also university lecturers, hold similar views. Sometimes you really wonder what a CS or software engineering degree is really good for. By the way, recursion and iteration are equivalent, which means that you can theoretically rewrite any recursive function as an iterative function, and vice versa.

I’ve met quite a few people who view recursion as an obscure alternative to simple loops and “something you don’t do in production code”. I was therefore wondering where this view might come from, and skimmed some introductory text books. The index of Bjarne Stroustrup’s Programming: Principles and Practice Using C++ doesn’t mention recursion at all. Y. Daniel Liang’s Introduction to Java Programming has a short chapter on recursion, but you’ll only find very basic examples there. Python is getting more popular as an introductory language, so I had a look at John M. Zelle’s Python Programming: An Introduction to Computer Science. In that book, recursion is covered in the very last chapter, which doubles as an introduction to the analysis of algorithms.

Zelle uses well-worn examples like computing factorials and Fibonacci numbers or checking whether a string is an anagram. Towers of Hanoi is in there, too. Recursion is also mentioned when describing sorting algorithms like merge sort. The problem I see with this is that the simpler examples don’t necessarily show any advantage of recursion. Towers of Hanoi is too specialized, and it’s not quite clear how that knowledge will transfer to any program you might write yourself. Lastly, sorting algorithms are normally presented as pseudo-code, and recursion is just part of some. In other words, this approach doesn’t necessarily invite exploration.

What’s missing are more elaborate and somewhat realistic problems that show how recursion can lead to cleaner code, and code that is much easier to reason about. Typical textbook examples normally don’t provide this. I’m not sure that fractals make a good example either. Sure, if you’re going to write a fractal generator, you might revisit your textbook and check how recursion is used there. However, there isn’t much of an application for it.

In short, none of the introductory textbooks mentioned give the impression that recursion may be a viable programming concept, and that it’s worth thinking about whether a certain problem might better be solved recursively, instead of making iteration the default choice. I was pleasantly surprised, though, to find a few neat problems in Allen B. Downey’s Think Python: How to Think Like a Computer Scientist. This book is quite astounding. It’s free, short, and content-wise it runs circles around your typical 1000+ page tome that is full of filler material.

Here is exercise 12.6, taken from version 2.0.10 (May 2013) of Think Python. Prof. Downey frequently updates that book, so the exercise may be modified, moved, or even removed from the book in the future. Therefore I’ll describe it fully.

The input is a list containing a good 100,000 words of the English language, and the desired output is the longest word that can be completely reduced. In this context, “reducing a word” means that a given word remains a valid word, i.e. a word contained in the word list, after removing a letter. You can remove a letter from anywhere in the word, but you cannot rearrange letters. The goal is to eventually end up with a one-letter word.

The example in the book is sprite, which leads to the following reduction:

sprite -> spite -> spit -> pit -> it -> i

So, what is the longest word in the English language that can be reduced in this manner? Feel free to grab the text file and try to figure it out yourself.

Prof. Downey gives the following hints:

Write a program to find all words that can be reduced in this way, and then find the longest one. This exercise is a little more challenging than most, so here are some suggestions:

1. You might want to write a function that takes a word and computes a list of all the words that can be formed by removing one letter. These are the “children” of the word.
2. Recursively, a word is reducible if any of its children are reducible. As a base case, you can consider the empty string reducible.
3. The wordlist I provided, words.txt, doesn’t contain single letter words. So you might want to add “I”, “a”, and the empty string.
4. To improve the performance of your program, you might want to memoize the words that are known to be reducible.

So, how would you do it? Give it a try, and you might find that recursion allows to write the most important function in a very succinct and elegant way, even though a large part of the program is iterative. Thus, it shows that recursion can be a useful addition to your toolbox, which is an impression you probably won’t get from computing factorials.

In my solution, which is reproduced below, I print out a list of the 20 longest words, but of course you can as well just return the first entry of the list.

def reduce_words():

    def create_dict():
        fin = open('words.txt')
        res = {}
        
        for line in fin:
            word = line.strip()
            res[word] = []
            
        for element in ["a", "i", ""]:
            res[element] = []

        return res

    def add_children(d):
        for key in d.keys():
            children = []
            for i in range(len(key)):
                candidate = key[:i] + key[i+1:]
                if candidate in d and candidate not in children:
                    children.append(candidate)
            d[key] = children
            
        return d

    def recursive_trails(d):
        res = []

        def helper(key, result):
            if d[key] == []:
                return
            if key in ["a", "i", ""]:
                res.append((len(result[0]), result))
            else:
                for entry in d[key]:
                    return helper(entry, result + [entry])
                
        for key,value in d.items():
            helper(key, [key])

        return res

    def top_n(results, n):
        results.sort(reverse = True)
        for i in range(n):
            print results[i]
                    
    d = create_dict()
    add_children(d)
    trails = recursive_trails(d)
    top_n(trails, 20)

reduce_words()

I thought that this was a really neat exercise that showed that you can use recursion in a pretty realistic problem, and end up with pretty elegant code. If only examples like this were included in standard introductory textbooks, or if instructors would use Prof. Downey’s book. But the textbook industry is shady, here is just one example, and the higher education industry complicit, so it may require another two or three financial crises until we see substantial rates of adoption of free high-quality textbooks.