Python Generator Vs Callback Function

I have a class that solves an exact cover problem using a recursive, backtracking algorithm. Originally, I implemented the class with a callback function I passed to the object dur

Solution 1:

What i meant in my comment, ("yielding from a recursive function sounds like it requires extra for loops to pass the results down to the caller") is this line:

          for tf in self.solve():
             yield tf

These lines recursively loop over the results from the deeper recursion stages. That means that a single result is iterated over on each level of the recursion, resulting in a lot of unnecessary looping.

Let me illustrate with this example:

n = 0
def rekurse(z):
    global n
    if z:
        yield z
        for x in rekurse(z-1):
            n += 1
            yield x

print list(rekurse(10))
print n

As you can see this simply counts down from 10, so you'd expect a a linear number of iterations. What you can see though is that n grows quadratically - recurse(10) loops over 9 items, recurse(9) over 8 items and so on.

The more items you have, the more time Python spends on these simple lines. Callbacks completely avoid that problem, so I'd suspect that is the problem with your code.

A optimized implementation of PEP 380 could fix this (see this paragraph). In the meantime I don't think it's a good idea to yield from recursive functions (at least if they recurse deeply), they just don't work well together.