Recursive generator in Python 3.5

[Steve D'Aprano]

On Tue, 1 Nov 2016 12:39 am, tpqnnd01 at gmail.com wrote:

> I have some confuse about the recursive generator where the code mixing
> Yield and return keywork as below. I understand that "return" keywork just
> raise StopIteration exception but can not understanding in depth, so,
> could some one explain me about the actual function of two "return"
> keyworks in case it have other function and mechanism of for running this
> code segment below:

What part confuses you? The recursion, or the generator?

In a generator, "yield" outputs a value. "return" ends the generator. Return
is optional: reaching the end of the generator is the same as return.

So this generator:

def gen():
    yield 1
    yield 2
    return  # optional


will output 1, then 2, then stop.

This generator:

def gen(*args):
    if not args:
        yield ""
        return
    for a in args:
       yield a
    return  # optional

will either output "", then stop, or it will output each of the arguments
given, then stop.

Now let's look at your recursive call version:


> def fg(args):
>   if not args:
>     yield ""
>     return
>   for i in args[0]:
>     for tmp in fg(args[1:]):
>       yield i + tmp
>   return

Let's start with a simple call:

list(fg([]))


args is empty, so it will output "" and halt.


list(fg(["ab"]))

args[0] is "ab", so it will loop:

    for c in "ab":

Inside this loop, it loops again, this time over the rest of the arguments.
There are no more arguments, so the recursive call to fg() will yield "".

So the generator outputs "a" + "" (which is "a"); then it outputs "b" + ""
(which is "b"). Then it halts.

Second example:

list(fg(["xy", "ab"]))

args[0] is "xy", so it will loop:

    for c in "xy":

Inside this loop, it loops again, this time over the rest of the arguments.
There is one more argument, "ab", so the recursive call to fg() is like:

fg(["ab"])

But we have already seen what happens when you call fg(["ab"]): it
outputs "a", then "b", then halts.

So now we have:

    for c in "xy":
        for d in ("a", "b"):
            yield c + d

so you will get "xa", "xb", "ya", "yb".



Last example:

list(fg(["PQR", "xy", "ab"]))

will loop over "PQR", then as the inner loop it will loop over
fg(["xy", "ab"]). But we already have seen that. So you will get:

"Pxa", "Pxb", "Pya", "Pyb",
"Qxa", "Qxb", "Qya", "Qyb",
"Rxa", "Rxb", "Rya", "Ryb"

and then halt.





-- 
Steve
“Cheer up,” they said, “things could be worse.” So I cheered up, and sure
enough, things got worse.