Python generator with recursive call

问题:

I am trying to yield nodes in a tree with a generator using a preorder depth first search. The parents node can have any number of children and the children are stored in a list.

I figured this code would work, but it appears that the for loop is iterating over each child without actually going into the recursive call.

def traverse_tree(t):
    yield t.label, t.val
    for child in t.children:
        traverse_tree(child)

Does anyone know how to handle this?

回答1:

If you look at the function, for each call, the yield expression only gets hit once. So your generator will only yield one thing. To get it to yield more than one thing, you need to yield from the children too:

def traverse_tree(t):
    yield t.label, t.val
    for child in t.children:
        yield from traverse_tree(child)

This is python 3.3+ syntax (IIRC). For earlier versions:

def traverse_tree(t):
    yield t.label, t.val
    for child in t.children:
        for label, val in traverse_tree(child):
            yield label, val

回答2:

Check out this answer Recursion using yield, and more specifically the yield from construction here: https://docs.python.org/3/whatsnew/3.3.html#pep-380.

回答3:

When you call the function that contains yield, the code in the body of the function does not run. Instead, it returns a generator object.

You can use a list to store the result instead:

def traverse_tree(t, list):
    list.append((t.label, t.val))
    for child in t.children:
        traverse_tree(child, list)