Recursion with loops

Anagrams

So far all our examples of recursion haven't been compelling: It's just as easy — or easier — to do the problem without using recursion. Now let's tackle a problem that recursion makes much easier.

The problem is to list all rearrangements of a sequence of letters. For example, given the word eat, the rearrangements include eat, eta, aet, ate, tea, and tae.

We do by writing a function that takes a string of letters and returns a list of all possible rearrangements. As before, our base case in when there is just one letter. In the recursive case, though, we'll produce all rearrangements by iterating through each letter, using recursion to produce all rearrangements of everything but all that letter, and then add each of those rearrangements into our result.

def get_anagrams(letters):
    if len(letters) <= 1:
        return [letters]
    else:
        result = []
        for i in range(len(letters)):
            out = letters[i]
            rest = letters[:i] + letters[i + 1:]
            for subgram in get_anagrams(rest):
                result.append(out + subgram)
        return result

For example, given the string eat, we first remove the letter e and recurse to get the list [at, ta], and we add e to each of those to add eat and eta to our list. Then we remove the letter a and recurse to get the list [et, te], and we add a to each of those to add aet and ate to our list. Finally we remove the letter t and recurse to get the list [ea, ae], and we add t to each of those to add tea and tae to our list. By the end, we have all six desired rearrangements in our list, which we can return.

For the four-letter string opts, we go through the following recursion tree.

Variables

We've depended on this before, but it's worth noting that as you go through the recursion, each recursive call gets its own set of variables. In the opts recursion tree, the top node has its result variable, and after recursing on pts, it adds several strings into result. Then it goes on to recurse on ots; the first thing to happen within that recursive call is to set result to the empty list. But this has so effect on opts's result — it just creates a separate result for ots, to which that recursive call eventually adds several strings. None of these are added to opts's result until the opts recursive call does it itself.