Question - What is a faster alternative to recursion?

[Stephen Thorne]

On Wed, 02 Mar 2005 00:58:58 -0600, actuary77
<actuary77 at elemental-systems.com> wrote:
> Yes, iteration is 10000000000 times faster than recursion.
> 
> The problem I have is:
> 
> # need to call this function 50 times with seed of 10
> (afunc(afunc(afunc(...       afunc(10))
> 
> required_iterations_ 50
> function:  afunc(x): x**.5 + 1000 * x + 46.
> initial_seed:    10
> 
> Result =>  afunc(afunc(afunc(afunc(afunc(afunc ...   (_aseed)
> 
> What is the fastest way to do this without using recursion?
> 
> With recursion:
> ================
> 
> def rec(afunc,n,x):
>      y = afunc(x)
>      if n == 0:
>          return y
>      else:
>          return rec(afunc,n-1,y)
> 
> def myfunc(x):
>      return x**.5 + 1000 * x + 46.
> 
> from time import time
> 
> _b=time()
> _y = rec(myfunc,50,10)
> _e=time()
> _t=_e-_b
> print "result: %r time: %f\n" % (_y,_t)
> 
> output:
> result: 1.00493118428005e+154 time: 0.030000
> 
> Is there a much faster way?

Sure.

[sthorne at wendy tmp]$ python timeit.py -s 'from recursive import
calculate' 'calculate(100, 10)'
1000 loops, best of 3: 295 usec per loop
[sthorne at wendy tmp]$ python timeit.py -s 'from iterative import
calculate' 'calculate(100, 10)'
10000 loops, best of 3: 134 usec per loop
[sthorne at wendy tmp]$ cat iterative.py

def calculate(repeats, value):
    for x in range(repeats):
        value = value ** .5 + 1000*x + 46
    return value

[sthorne at wendy tmp]$ cat recursive.py
def rec(afunc,n,x):
    y = afunc(x)
    if n == 0:
        return y
    else:
        return rec(afunc,n-1,y)

def myfunc(x):
    return x**.5 + 1000 * x + 46.

def calculate(repeats, value):
    rec(myfunc, repeats, value)


As you can see, the iterative solution actually results in less code too ;)

Stephen.