Do we create n iterators when we use yield recursively?

user_891814 0
Viewed 87

Consider:

def iterInOrder(node):
    if node.left:
        for n in iterInOrder(node.left):
            yield n
    yield node
    if node.right:
        for n in iterInOrder(node.right):
            yield n

And let n be number of nodes in the input binary tree, Do we create a single generator that yields n nodes? Or do we create n iterators that each generate a node? what can you say about space/time complexity of that code comparing to a simple recursive travel:

def visitInOrder(node):
    if node.left:
        visitInOrder(node.left)
    visit(node)
    if node.right:
        visitInOrder(node.right)

I care more for Python 2, but may be nice to know if answer differs for Python 3.

python
1 Answers

In CPython, each call to iterInOrder() creates a new generator-iterator, regardless of Python version, and regardless of whether it's a top-level or recursive call.

Similarly, each call to visitInOrder() creates a new stack frame, again regardless of Python version or context.

So the space complexity is O(depth(tree)) either way (which doesn't have a useful relation, in general, to the number of nodes - the tree may be n levels deeps, or 2 levels deep).

Time is a different calculation, but subtle because it's barely ever noticeable: the recursive version has O(n) time complexity, but that's a lower bound on the generator version. Each time you yield, the yielded value is passed up the chain of recursive generator calls, one level at a time, until it's finally consumed by the top-level call. Then, when the chain is resumed, the stack of generator-iterator frames is reactivated one at a time, until getting back down to the original yield.

So in the generator version there is a time component quadratic in depth(tree). But unless the tree is very deep, you'll probably never notice that, because in CPython all that stack unwinding and rewinding occurs "at C speed".

user_27055420
Related