Recursion using yield

Question

Is there any way to mix recursion and the yield statement? For instance, a infinite number generator (using recursion) would be something like:

def infinity(start):
    yield start
    # recursion here ...

>>> it = infinity(1)
>>> next(it)
1
>>> next(it)
2

I tried:

def infinity(start):
    yield start
    infinity(start + 1)

and

def infinity(start):
    yield start
    yield infinity(start + 1)

But none of them did what I want, the first one stopped after it yielded start and the second one yielded start, then the generator and then stopped.

NOTE: Please, I know you can do this using a while-loop:

def infinity(start):
    while True:
        yield start
        start += 1

I just want to know if this can be done recursively.

See [here][1] for a good answer to this question I posed a while back. [1]: http://stackoverflow.com/questions/5704220/python-generator-vs-callback-function — sizzzzlerz, Jan 24 '12 at 18:18
Note: the proper way to do this would be to use [`itertools.count`](http://docs.python.org/dev/library/itertools.html#itertools.count) rather than roll your own solution, loop-based or othersise. — Petr Viktorin, Jan 24 '12 at 18:35
@PetrViktorin this is just an example, generating infinite numbers is not at all the real problem — juliomalegria, Jan 24 '12 at 18:52

score 193 · Accepted Answer · edited Jul 13 '16 at 22:26

193

Yes, you can do this:

def infinity(start):
    yield start
    for x in infinity(start + 1):
        yield x

This will error out once the maximum recursion depth is reached, though.

Starting from Python 3.3, you'll be able to use

def infinity(start):
    yield start
    yield from infinity(start + 1)

If you just call your generator function recursively without looping over it or yield from-ing it, all you do is build a new generator, without actually running the function body or yielding anything.

See PEP 380 for further details.

edited Jul 13 '16 at 22:26

user2357112

260,549
28
431
505

answered Jan 24 '12 at 18:14

Sven Marnach

574,206
118
941
841

16

But it seems with `yield from` there is still a recursion limit :( – Jo So Feb 15 '16 at 21:02
9

there will always be a recursion limit – Radio Controlled Jan 10 '20 at 10:36

score 13 · Answer 2 · edited Jun 18 '18 at 13:19

In some cases it might be preferable to use a stack instead of recursion for generators. It should be possible to rewrite a recursive method using a stack and a while loop.

Here's an example of a recursive method which uses a callback and can be rewritten using stack logic:

def traverse_tree(callback):
    # Get the root node from somewhere.
    root = get_root_node()
    def recurse(node):
        callback(node)
        for child in node.get('children', []):
            recurse(child)
    recurse(root)

The above method traverses a node tree where each node has a children array which may contain child nodes. As each node is encountered, the callback is issued and the current node is passed to it.

The method could be used this way, printing out some property on each node.

def callback(node):
    print(node['id'])
traverse_tree(callback)

Use a stack instead and write the traversal method as a generator

# A stack-based alternative to the traverse_tree method above.
def iternodes():
    stack = [get_root_node()]
    while stack:
        node = stack.pop()
        yield node
        for child in reversed(node.get('children', [])):
            stack.append(child)

(Note that if you want the same traversal order as originally, you need to reverse the order of children because the first child appended to the stack will be the last one popped.)

Now you can get the same behavior as traverse_tree above, but with a generator:

for node in iternodes():
    print(node['id'])

This isn't a one-size-fits-all solution but for some generators you might get a nice result substituting stack processing for recursion.

Nice answer! Yield in python 2.7 can not really be used with recursion, but by manually managing the stack you can get the same effect. — 00prometheus, Oct 08 '17 at 20:07

score 3 · Answer 3 · edited Jul 26 '20 at 19:44

3

def lprint(a):
    if isinstance(a, list):
        for i in a:
            yield from lprint(i)
    else:
        yield a

b = [[1, [2, 3], 4], [5, 6, [7, 8, [9]]]]
for i in lprint(b):
    print(i)

edited Jul 26 '20 at 19:44

Macke

24,812
7
82
118

answered Jul 24 '19 at 09:23

Юрий Блинков

47
2

What is `b`? Try not to leave code-only answers... A little clarification and explanation will help to put things in context and better understand your answer – Tomerikoo Jul 24 '19 at 12:26
for i in lprint(a): print(i) – Юрий Блинков Jul 25 '19 at 01:42
Why not edit the answer so it is more clear? You can do it by clicking the little `edit` tag below your answer or click [here](https://stackoverflow.com/posts/57179489/edit). Also, as I said try to add a little explanation for how and why this solves the problem – Tomerikoo Jul 25 '19 at 10:12
`yield from` is what I was looking for. Thanks! – tarikki Nov 27 '22 at 05:37

Recursion using yield

3 Answers3

Linked

Related