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.

The final project of Coursera’s Introduction to Systematic Program Design – Part 1 was to write a solver for the four queens problem. The goal is to place four queens on a 4 x 4 chess board so that the queens do not obstruct each other. This problem is a simplification of the eight queens problem, and it’s a good exercise for backtracking search. Please note that the Coursera course was using a Lisp dialect as its teaching language. Due to the Coursera honor code I cannot share that solution. However, since some students attempted to rewrite their solution in Python and discussed their approaches on the forum, I decided to port my solution to Python as well and present it here.

Given the limited problem space, there are other approaches to the four queens problem that may be more effective. Those may not teach you about constraint programming or backtracking search, though, and they probably don’t scale that well either. Just have a look at a 4 x 4 chess board: If you have the insight to put the first queen on the second square, then the problem basically solves itself!

To make it a bit easier to transition between the problem description and the eventual Python code, I’ll describe the positions on the board as integers, and not as a letter-integer pair as you’d see it on the chess board. The board therefore turns into:

 0  1  2  3
 4  5  6  7
 8  9  10 11
 12 13 14 15 

Let’s assume you want to implement a proper backtracking algorithm. Say, you start with an empty board. What would you then do? The key idea is to check every square and if this turns out to be unfeasible further down the line, discard that branch of the emerging solution tree and continue from a point that has not yet been explored. Concretely, this means that after the very first iteration of the program, when given an empty board, you’ve created a list of 16 boards, each containing a queen on a different square. The first board in the list has the queen on position 0, the second on position 1, and so on.

Let’s stick with the very first board for the time being. In the second iteration you’d create another list of boards that all contain one queen on square 0, and the second queen on one of the squares 6, 7, 9, 11, 12, 14. Pick any of those boards, put a third queen on them, and you’ll find that it is impossible to place a fourth queen. Seeing that it’s not possible to solve the 4-queens problem if you start with a queen on square 0, you then move on to the next square and try to solve the problem. This is indeed one of the solutions, so the algorithm should present a valid board at the end.

Having illustrated the problem, let’s now talk about one way to code up the solution in Python. I tend to avoid overly terse expressions, apart from a list comprehension here or there, so it should be readable with just a bit of commentary.

To make life a bit easier and the resulting code more readable, I made the following definitions:

B = False
Q = True
all_positions = range(16)

The variable “all_positions” is nothing but a veneer to make the code more legible. It represents the idea that the board is a list with 16 entries.

You might think that it’s silly to define B (for blank) as False and Q (for Queen) as True. However, you can then define a board more succinctly in list form. Here’s what the empty board looks like:

BD0 = [B, B, B, B,
       B, B, B, B,
       B, B, B, B,
       B, B, B, B,]

This list gets evaluated to a list with sixteen “False” entries, but the shorthand introduced above saves some typing and allows for easier illustration of the problem.

A queen attacks in three directions over the whole extent of the board, i.e. horizontally, vertically, and diagonally. Since the board is represented as a list of boolean values, and Python allows for index-based list access, the following definitions can be used to traverse the board easily and check whether there are any collisions:

rows = [ [  0,  1,  2,  3 ],
         [  4,  5,  6,  7 ],
         [  8,  9, 10, 11 ],
         [ 12, 13, 14, 15 ] ]

columns = [ [ 0,  4,  8, 12 ],
            [ 1,  5,  9, 13 ],
            [ 2,  6, 10, 14 ],
            [ 3,  7, 11, 15 ] ]

diagonals = [ [  1,  4 ],
              [  2,  5,  8 ],
              [  3,  6,  9, 12 ],
              [  7, 10, 13 ],
              [ 11, 14 ],
              [  2,  7 ],
              [  1,  6, 11 ],
              [  0,  5, 10, 15 ],
              [  4,  9, 14 ],
              [  8, 13] ]

Please note that this solution does not scale well. It works fine on a 4 x 4 board, but to extend it to an 8 x 8 board, you’d either have to expand the lists with fitting numerical values, or find a way to represent rows, columns, and diagonals as sequence definitions that can be generated automatically, but that’s a problem to look into later. Currently, I’m primarily concerned with an illustration of that particular search problem.

With the preliminaries behind us, I’ll now focus on a general strategy for solving the problem, before filling in the blanks and showing you the source code. The following also serves as a blueprint if you want to go ahead and write the program yourself. I prefer to decompose functions so that they, ideally, achieve one task only. This leads to a greater number of functions, but it makes it easier to reason over code, to debug, and to extend the program later on.

Following the description above, the main steps are something like this:

• 1. enter a starting position (board)
• 2. if that board is solved, return the board
• 3. else: generate a list of boards with all valid subsequent positions, and continue with 1)

This gives rise to the question when a board is valid. To make the code a bit cleaner, I’ll assume that the set of inputs only consists of well-formatted lists, according to the previous specification. A board is valid if there is at most one queen in every column, row, and diagonal, which can be expressed like this:

def board_valid(board):

    def check_entries(entries):
        for entry in entries:
            if number_of_queens(board, entry) > 1:
                return False
        return True
    
    return all([ check_entries(x) for x in [ rows, columns, diagonals ] ])

The function number_of_queens() is defined separately:

def number_of_queens(board, positions):
    return sum([ 1 for pos in positions if board[pos] ])

A board is solved if it is a valid board and if there are exactly four queens on the board:

def board_solved(board):
    return isinstance(board, list) and board_valid(board) \
            and number_of_queens(board, all_positions) == 4 

With those functions in place, everything is set up to solve the problem. I tend to prefer a bottom-up approach when programming, and I visually represent this by putting the most general function last.

# find all empty squares
def get_positions(board):
    return [ x for x in range(len(board)) if not board[x] ]

def get_next_boards(board, positions):
    result = []
    for pos in positions:
        temp = copy.deepcopy(board)
        temp[pos] = True
        result.append(temp)
    return [ board for board in result if board_valid(board) ]

def solve_board(board):
    if board_solved(board):
        return board
    else:
        return solve_board_list(get_next_boards(board, get_positions(board)))
        
def solve_board_list(board_list):
    if board_list == []:
        return False
    else:
        check = solve_board(board_list[0])
        if board_solved(check) != False:
            return check
        else:
            return solve_board_list(board_list[1:])

I think this is quite readable. If the flow of execution is not quite clear, please refer to the description of the problem at the start of the article. Congratulations! You’ve now solved the four queens problem using backtracking search.

The entire code, with test cases and some further helper functions, like a visualizer, a generator for all valid starting positions, and a function that outputs all possible solutions, is available on my github page. Look for the file “4_queens.py”.