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.
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.