Recursive Generators in Python

Today we’ll be talking about recursive generators.

Here’s the video version of the article:

If you haven’t read my previous four articles on generators (basics of generators, sending objects to generators, the throw method and the yield from statement), it’s definitely recommended to do so before you go on with this one.  

I also have an article on recursive functions, so feel free to read it too, if you’re not sure what recursion is all about.

Just like regular functions, generators may be recursive, which means they can call themselves inside their function body.

A good example to demonstrate it is a generator that creates all the permutations of the letters of a string. A permutation is a rearrangement of all the elements of an ordered sequence. So, the sequence a, b has just 2 permutations:

The sequence a, b, c has six permutations:

The longer the sequence, the more permutations there are. We can calculate the exact number of permutations of a sequence by finding its factorial. So, if we have 2 elements in a sequence, there are 2! = 1 * 2 = 2 permutations, as shown above. If we have 3 elements, the number of permutations is equal to 3! = 1 * 2 * 3 = 6, as shown above as well. If we had a sequence consisting of 5 elements, there would be 5! = 1 * 2 * 3 * 4 * 5 = 120 permutations. Generally a sequence of n elements has n! permutations:

Although Python is rich in modules that make mathematical stuff easier to handle, and, naturally, there is a module where a special function to create permutations exists (the itertools module), this section is about recursive generators, so we’ll choose the harder path.

So, let’s write the code that will print all the permutations of the letters in a word:

def permutation_generator(word):
    if len(word) == 0:
        yield ""
    else:
        for m in range(len(word)):
            for n in permutation_generator(word[:m] + word[m + 1:]):
                yield word[m] + n

for x in permutation_generator("home"):
    print(x)

And here’s the output:

home
hoem
hmoe
hmeo
heom
hemo
ohme
ohem
omhe
omeh
oehm
oemh
mhoe
mheo
mohe
moeh
meho
meoh
ehom
ehmo
eohm
eomh
emho
emoh

This code yields one letter and recursively finds the permutations of the remaining letters, adding them to the first letter. Then the same is repeated for each letter until all combinations are found.

To visualize the first couple of examples. Here’s how it works: