performance of recursive generator

[Steven Bethard]

aurora wrote:
> This test somehow water down the n^2 issue. The problem is in the depth 
> of  recursion, in this case it is only log(n). It is probably more 
> interesting  to test:
> 
> def gen(n):
>      if n:
>          yield n
>          for i in gen(n-1):
>              yield i

You should be able to do this yourself ;) but here's the results anyway:

-------------------- test.py --------------------
def gen(n):
     if n:
         yield n
         for i in gen(n-1):
         	yield i

def gen_wrapper(n):
     return list(gen(n))

def nongen(n, func):
	if n:
	    func(n)
	    nongen(n-1, func)

def nongen_wrapper(n):
	result = []
	nongen(n, result.append)
	return result
-------------------------------------------------

D:\steve>python -m timeit -s "import test" "test.gen_wrapper(10)"
10000 loops, best of 3: 22.3 usec per loop

D:\steve>python -m timeit -s "import test" "test.nongen_wrapper(10)"
100000 loops, best of 3: 12 usec per loop

D:\steve>python -m timeit -s "import test" "test.gen_wrapper(20)"
10000 loops, best of 3: 60.8 usec per loop

D:\steve>python -m timeit -s "import test" "test.nongen_wrapper(20)"
10000 loops, best of 3: 20.9 usec per loop

D:\steve>python -m timeit -s "import test" "test.gen_wrapper(100)"
1000 loops, best of 3: 1.01 msec per loop

D:\steve>python -m timeit -s "import test" "test.nongen_wrapper(100)"
10000 loops, best of 3: 93.3 usec per loop

It does appear that you get O(N**2)-ish behavior, but the difference 
isn't horribly noticeable at a depth of 10 or 20.  How deep are your trees?

I also have to mention that, for this kind of problem, it's silly to use 
any recursive solution, when there's a faster non-recursive solution:

-------------------- test.py --------------------
...
def nonrecur(n):
     result = []
     append = result.append
     while n:
         append(n)
         n -= 1
     return result
-------------------------------------------------

D:\steve>python -m timeit -s "import test" "test.nonrecur(10)"
100000 loops, best of 3: 6.26 usec per loop

D:\steve>python -m timeit -s "import test" "test.nonrecur(100)"
10000 loops, best of 3: 37.9 usec per loop

Sure, this only works on non-branching trees, but if that's what you're 
worried about, use the solution designed for it. ;)

STeVe