# performance of recursive generator

Steven Bethard steven.bethard at gmail.com
Thu Aug 11 22:01:54 CEST 2005

```aurora wrote:
> I love generator and I use it a lot. Lately I've been writing some
> recursive generator to traverse tree structures. After taking closer
> look  I have some concern on its performance.
>
> Let's take the inorder traversal from
> http://www.python.org/peps/pep-0255.html as an example.
>
> def inorder(t):
>     if t:
>         for x in inorder(t.left):
>             yield x
>         yield t.label
>         for x in inorder(t.right):
>             yield x
>
> Consider a 4 level deep tree that has only a right child:
>
> 1
>  \
>   2
>    \
>     3
>      \
>       4
>
>
> Using the recursive generator, the flow would go like this:
>
> main    gen1        gen2        gen3        gen4
> ----------------------------------------------------
>
> inorder(1..4)
>
>         yield 1
>         inorder(2..4)
>                     yield 2
>         yield 2
>                     inorder(3..4)
>                                 yield 3
>                     yield3
>         yield 3
>                                 inorder(4)
>                                             yield 4
>                                 yield 4
>                     yield 4
>         yield 4
>
>
> Note that there are 4 calls to inorder() and 10 yield. Indeed the
> complexity of traversing this kind of tree would be O(n^2)!

You seem to be assuming that a yield statement and a function call are
equivalent.  I'm not sure that's a valid assumption.

Anyway, here's some data to consider:

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

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

def nongen(n, func):
if n:
nongen(n/2, func)
func(n)
nongen(n/2, func)

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

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

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

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

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

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

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

The non-generator version is consistently faster, somewhere around twice
as fast.

Of course, I'll still be writing generator-based solutions util I'm
certain the recursion's the speed bottleneck in my application.

STeVe

```