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 -- http://mail.python.org/mailman/listinfo/python-list