Does "yield" in Python go up the call stack when using recursion?

Question

While I am studying Bill Lubanovic's Introducing Python, I modified some code to understand flatten() function in chapter 9.

def flatten(lol):
    for item in lol:
        if isinstance(item, list):
            for subitem in flatten(item):
                print('yield1 ', subitem)
                yield subitem
        else:
            print('yield2 ', item)
            yield item

lol = [1, 2, [3, 4, 5], [6, [7, 8, 9],[]]]
list(flatten(lol))

I expected output is

('yield2 ', 1)
('yield2 ', 2)
('yield2 ', 3)
('yield2 ', 4)
('yield2 ', 5)
('yield1 ', 3)
('yield1 ', 4)
('yield1 ', 5)
...
...(skipped)

but the correct output of the program like this:

('yield2 ', 1)
('yield2 ', 2)
('yield2 ', 3)
('yield1 ', 3)
('yield2 ', 4)
('yield1 ', 4)
('yield2 ', 5)
('yield1 ', 5)
...
...(skipped)

I can't understand why "('yield1 ', 3)" was printed before ('yield2 ', 4), even though the loop in inner flatten() called is not over yet. I want to know if the 'yield' does stack unwinding when recursion.

The title mentions recursion. There's no recursion in the function you posted. Did you copy it correctly? — Barmar, Jul 31 '21 at 06:52
This post pretty much covers everything you need to know about `yield` https://stackoverflow.com/questions/231767/what-does-the-yield-keyword-do — pyeR_biz, Jul 31 '21 at 06:53
It's unrelated to your actual question, but the output you're showing, with 2-tuples in parentheses suggests that you're using Python 2 to run your code while writing something intended for Python 3. Python 3 is really the way to go, so I'd suggest upgrading your version of Python if you can (you might already have Python 3 in addition to Python 2, you might just need to call it by `python3` or something). — Blckknght, Jul 31 '21 at 07:34

ThePyGuy · Answer 1 · 2021-07-31T07:28:55.533

2

When you are iterating for subitem in flatten(item), the call goes back to flatten and it prints the item first yield2 value, then you are printing it again using yield1 value inside the loop, that's why, it is being printed twice once for yield1 and once for yield2, and it is not going up the stack as you have mentioned in the question title.

On a side note, using yield from ... is recommended way to make a recursive call back to the generator, rather than iterating generator call manually.

def flatten(lol):
    for item in lol:
        if isinstance(item, list):
            yield from flatten(item)
            # for subitem in flatten(item):
            #    print('yield1 ', subitem)
            #     yield subitem
        else:
            print('yield2 ', item)
            yield item

lol = [1, 2, [3, 4, 5], [6, [7, 8, 9], []]]
list(flatten(lol))

OUTPUT:

yield2  1
yield2  2
yield2  3
yield2  4
yield2  5
yield2  6
yield2  7
yield2  8
yield2  9

[1, 2, 3, 4, 5, 6, 7, 8, 9]

edited Jul 31 '21 at 07:28

answered Jul 31 '21 at 07:01

ThePyGuy

17,779
5
18
45

2

That's the right way to do it. It would be nice if `yield from` were implemented as a true coroutine, with context switching directly from the recursive instance to the top-level caller rather than going up and down the call stack each time, but at present it's a missing optimization (`yield from f()` is equivalent to `for v in f(): yield v`, both in effect and in the implementation). Maybe they'll improve it in the future. But it works, and isn't too bad as long as the recursion depth isn't too great. – Tom Karzes Jul 31 '21 at 07:05
Thank you for answering. I have to figure out more about it. – dragor0123 Jul 31 '21 at 07:07
The first statement in this answer is flat wrong. There's no need for `yield from` to recurse, you can just do normal recursion while iterating if you want, as in the original code. Indeed, you *need* to do that if you want to do something special on each level of the recursive stack for each item (like printing it). Now, `yield from` is indeed generally the right thing to do in general, when you *don't* have anything to do on that level, but for this question speaking about it is missing the point. – Blckknght Jul 31 '21 at 07:20
@Blckknght, you are also right, so I just changed the language a bit. – ThePyGuy Jul 31 '21 at 07:29

score 1 · Accepted Answer · answered Jul 31 '21 at 07:30

Yes, a yield statement suspends the execution of the current function and gives control of the program to the calling code, where the yielded item will be the next value from the generator as it is being iterated. Only when a further value is requested from the generator will the inner call of the function resume.

You might understand things better if you tried a smaller input and tried iterating it manually with next():

>>> gen = flatten([[1, [2]], 3])

>>> print("output", next(gen))
yield2  1
yield1  1
output 1

>>> print("output", next(gen))
yield2  2
yield1  2
yield1  2
output 2

>>> print("output", next(gen))
yield2  3
output 3

>>> print("output", next(gen))
Traceback (most recent call last):

  File "<ipython-input-16-1c675fe35f03>", line 1, in <module>
    print("output", next(gen))

StopIteration

Thanks to you, I understood the concept! – dragor0123 Jul 31 '21 at 07:40 — dragor0123, Jul 31 '21 at 07:40

Does "yield" in Python go up the call stack when using recursion?

2 Answers2