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?

If you're new to recursion look at some simpler examples of it first. — Alex Hall, Jun 05 '16 at 19:30
The recursive things mix up with 'yield' which drives me crazy. But , anyway, thank you for your answer. — Dr.Bit, Jun 05 '16 at 19:51
If you cannot understand the combination of recursion and generators it means you don't properly understand one of those two parts. — Alex Hall, Jun 05 '16 at 20:00

score 4 · Accepted Answer · answered Jun 05 '16 at 19:51

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.

Thank you for your answer. This one is very clear to me. – Dr.Bit Jun 06 '16 at 01:35 — Dr.Bit, Jun 06 '16 at 01:35

Will Ness · Answer 2 · 2016-06-05T22:37:01.130

When you call a function that returns, it disappears after having produced its result.

When you ask a generator for its next element, it produces it (yields it), and pauses -- yields (the control back) to you. When asked again for the next element, it will resume its operations, and run normally until hitting a yield statement. Then it will again produce a value and pause.

Thus calling a generator with some argument causes creation of actual memory entity, an object, capable of running, remembering its state and arguments, and producing values when asked.

Different calls to the same generator produce different actual objects in memory. The definition is a recipe for the creation of that object. After the recipe is defined, when it is called it can call any other recipe it needs -- or the same one -- to create new memory objects it needs, to produce the values for it.

This is a general answer, not Python-specific.

score 0 · Answer 3 · edited May 23 '17 at 10:33

Thanks for the answers. It really helps me to clear my mind and now I want to share some useful resources about recursion and generator I found on the internet, which is also very friendly to the beginners.

To understand generator in python. The link below is really readable and easy to understand. What does the "yield" keyword do in Python?
To understand recursion, "https://www.youtube.com/watch?v=MyzFdthuUcA". This youtube video gives a "patented" 4 steps method to writing any recursive method/function. That is very clear and practicable. The channel also has several videos to show people how does the recursion works and how to trace it.

I hope it can help someone like me.

you can accept one of the answers, that was the most helpful to you. — Will Ness, Jun 06 '16 at 09:29

How do Python Recursive Generators work?

3 Answers3