CODEWITHSUNDEEP
pythonrecursiongeneratortime-complexity
xpilot
xpilot

Reputation: 1019

Python recursive yield asymptotic runtime

I'm writing a recursive generator function that basically looks like this:

def f(n):
  if n > 0:
    for i in f(n-1):
      yield i
  yield n

This has runtime O(n^2). Sadly, the python3 (3.3) version

def f(n):
  if n > 0:
    yield from f(n-1)
  yield n

suffers the same problem. Clearly, this iteration should only take O(n) time. Any ideas?

Upvotes: 2

Views: 241

Answers (1)

user7610
user7610

Reputation: 28879

The problem you describe has been considered in PEP 380 and it noted that optimization of the recursive yield from such as you suggest could be performed by a Python language implementation.

Using a specialised syntax opens up possibilities for optimisation when there is a long chain of generators. Such chains can arise, for instance, when recursively traversing a tree structure. The overhead of passing next() calls and yielded values down and up the chain can cause what ought to be an O(n) operation to become, in the worst case, O(n**2).

Apparently, CPython 3 cannot optimize this, and the yield from becomes just a syntactic sugar for the explicit loop you have in your Python 2.7 code.

Upvotes: 1

Related Questions