How do Python Recursive Generators work?

Question

In a Python tutorial, I've learned that

Like functions, generators can be recursively programmed. The following example is a generator to create all the permutations of a given list of items.

def permutations(items):
    n = len(items)
    if n==0: yield []
    else:
        for i in range(len(items)):
            for cc in permutations(items[:i]+items[i+1:]):
                yield [items[i]]+cc

for p in permutations(['r','e','d']): print(''.join(p))
for p in permutations(list("game")): print(''.join(p) + ", ", end="")

I cannot figure out how it generates the results. The recursive things and 'yield' really confused me. Could someone explain the whole process clearly?

Answer 1

There are 2 parts to this --- recursion and generator. Here's the non-generator version that just uses recursion:

def permutations2(items):
    n = len(items)
    if n==0: return [[]]
    else:
        l = []
        for i in range(len(items)):
            for cc in permutations2(items[:i]+items[i+1:]):
                l.append([items[i]]+cc)
        return l

l.append([item[i]]+cc) roughly translates to the permutation of these items include an entry where item[i] is the first item, and permutation of the rest of the items.

The generator part yield one of the permutations instead of return the entire list of permutations.