Just occasionally, one would be quite lost without recursion

This was originally posted to Posterous in two parts, on the 23 and 26 August 2010. I don’t agree with all of it now, and I’m not sure it was worth writing in the first place, but I’ll keep it for the sake of continuity.

Last week I wrote a recursive function, and next to it I was moved to remark:

# Just occasionally, one would be quite lost without recursion

It’s pretty unusual to encounter a problem that is best solved using recursion. I suppose traversing a recursively-defined data structure, like a tree, is a good example – but it’s telling that good examples of recursive code are so rare that shockingly bad examples are often used.

But there is one problem that sometimes comes up, in various guises, for which recursion is the most natural solution. The first time I came across this was at school. We had a network of BBC micros, where you needed a password to log in, so of course I tried to write a simple brute-force password cracker in BBC BASIC so I could find out my friends’ passwords. I think the passwords were case-insensitive, and thirteen-year-olds didn’t use numbers or funny symbols in their passwords in those days, so I just needed to go through all the possible strings of letters.

I realised it was pretty easy to generate all the words of a particular length, using nested loops. In Python, it would be something like this:

# I hate that Python doesn't let you say 'A' .. 'Z' or something
letters = [ chr(i) for i in range(ord('A'), ord('Z') + 1) ]

def three_letter_words():
  for first_letter in letters:
    for second_letter in letters:
      for third_letter in letters:
        yield first_letter + second_letter + third_letter

and you can easily extend that to any number of letters you like. But wouldn’t it be nice to have a function, perhaps called n_letter_words, that let you specify a length and generated all the words of that length rather than just writing a bunch of different functions for different lengths of word?

I don’t think I figured out how to do it at the time, but a year or two later I did realise the trick was recursion. In other words, something like this:

def n_letter_words(n):
   if n == 0:
       yield ""
   else:
       for word in n_letter_words(n-1):
           for letter in letters:
               yield word + letter

Nothing complicated, but it would be a pain without recursion.

I honestly think that’s, in essence, the only recursive algorithm I’ve ever used in day-job code. The problem I had last week was to generate a table of all possible combinations of answers to a series of multiple-choice questions. The real code is in Javascript, but in Python it would look like this:

def combinations_of_answers(questions, answers):
    if not questions:
        yield []
     else:
         questions, question = questions[:-1], questions[-1]
         for row in combinations_of_answers(questions, answers):
             for answer in answers
: yield row +

PS. Of course I’m talking about mainstream programming languages here: Python, Java, C, that sort of thing. I’m not talking about Haskell, because (like almost everyone) I don’t actually use it for real work.

Addendum on Python generators

Recently I talked about the only recursive function I regularly write, but something about it nagged at me. The example Python code in the post looked simpler than the Javascript code that inspired it, and I wondered why. Most obviously, the Javascript function had an extra argument that wasn’t in the Python version.

In the Python examples, I used generator functions without thinking much of it, because they are the natural way to write that sort of code in Python. What I hadn’t consciously realised is that generators are particularly powerful when combined with recursion, and allow a more substantial simplification of the code. When you remove the generators, you find you need an additional function argument, as I had in my Javascript code.

The way I think of generators is that they let you invert the control flow. Instead of writing a function process_each_thing that takes a function argument, and is used like so:

def process_thing(thing):
    "Process the thing"
for_each_thing(process_thing)

you can instead write a generator each_thing that can be used more simply:

for thing in each_thing():
    "Process the thing"

Python’s lack of anonymous functions amplifies the advantage of the generator approach, but there is a straightforward procedure for translating from one style to the other. When you’re using recursion, though, the non-generator version starts to look quite complicated. Let’s take the example I used before:

def n_letter_words(n):
    if n == 0:
        yield ""
    else:
        for word in n_letter_words(n-1):
            for letter in letters:
                yield word + letter

and rewrite it without generators, using a function argument instead:

def for_each_n_letter_word(n, f):
    if n == 0:
        f("")
    else:
        def f1(word):
            for letter in letters:
                f(word + letter)
        for_each_n_letter_word(n-1, f1)

That isn’t too terrifying, but I would certainly need to ponder for a minute to understand what it was doing. Once you have that, it’s natural to try and replace the recursively-defined nested function with some simpler data structure. In this example each function essentially represents a suffix of the word, so the function argument can be replaced with an ”accumulator” string, as in:

def print_each_n_letter_word(n, acc=""):
    if n == 0:
        print acc
    else:
        for letter in letters:
            print_each_n_letter_word(n-1, acc + letter)

Which is pretty much the structure of the Javascript code I started with – and now I understand why it needed an extra argument.

This entry was posted in chatter. Bookmark the permalink.

One Response to Just occasionally, one would be quite lost without recursion

  1. Veky says:

    > # I hate that Python doesn’t let you say ‘A’ .. ‘Z’ or something

    Because you have something better.

    from string import ascii_uppercase as letters

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s