Help- Recursion v. Iter Speed comparison

[Robert Kern]

actuary77 wrote:

> Recurse from 9999 time: 4.3059999942779541 seconds
> 
> Iter from 9999 time: 0.0099999904632568359 seconds
> 
> No comparison, why is recursion so slow?

I usually don't delve too deeply into language design issues, so I hope 
others will correct me if I'm wrong. Recursion is usually slower than 
the equivalent iteration unless if it is specifically optimized by the 
language implementation. Most Schemes, for example, do tail-call 
optimization, and so many uses of recursion run pretty fast. CPython is 
not one of those implementations.

> Would using a generator be faster than recursion?

Try it.

> I really have complex list comprehension.

Then you shouldn't be using list comprehensions.

> I am interating n times.
> I have initial function: func(x)
> I have initial seed value:  _aseed
> 
> 
> iteration   value
>   1        func(_aseed)
>   2        func(func(_aseed))
>  ....
>   n       func(func(func...........(_aseed))
> 
> 
> What would be the fastest way to do this?

Non-generator:
def f1(aseed):
     values = [func(aseed)]
     for i in range(n-1):
         values.append(func(values[-1]))
     return values

Generator:
def f2(aseed):
     value = func(aseed)
     for i in range(n):
         yield value
         value = func(aseed)

Probably not *the* fastest solutions, but I'll wager that the speed 
gains you get from a faster solution will be more than paid for by a 
loss in clarity.

Do the simplest thing that could possibly work. Don't bother with 
trickier/less Pythonic approaches until they're really called for.

-- 
Robert Kern
rkern at ucsd.edu

"In the fields of hell where the grass grows high
  Are the graves of dreams allowed to die."
   -- Richard Harter