Help- Simple recursive function to build a list
I am trying to write simple recursive function to build a list: def rec(n,alist=[]): _nl=alist[:] print n,_nl if n == 0: print n,_nl return _nl else: _nl=_nl+[n] rec(n-1,_nl) _nl=[] _nl=rec(4) print _nl ### shouldn't this work? _nl=rec(4) The output is: 4 [] 3 [4] 2 [4, 3] 1 [4, 3, 2] 0 [4, 3, 2, 1] 0 [4, 3, 2, 1] None None Question: Why isn't the function returning a list? Why is function returning None? Any guidance from one of you pro's would be greatly appreciated. Thanks, DKoch [EMAIL PROTECTED] -- http://mail.python.org/mailman/listinfo/python-list
Re: Help- Simple recursive function to build a list - Sorry for all the noise!
actuary77 wrote: I am trying to write simple recursive function to build a list: def rec(n,alist=[]): _nl=alist[:] print n,_nl if n == 0: print n,_nl return _nl else: _nl=_nl+[n] rec(n-1,_nl) _nl=[] _nl=rec(4) print _nl ### shouldn't this work? _nl=rec(4) The output is: 4 [] 3 [4] 2 [4, 3] 1 [4, 3, 2] 0 [4, 3, 2, 1] 0 [4, 3, 2, 1] None None Question: Why isn't the function returning a list? Why is function returning None? Any guidance from one of you pro's would be greatly appreciated. Thanks, DKoch [EMAIL PROTECTED] Sorry for all of the noise! It now makes sense if I write it, (simple): def rec2(n): if n == 0: return [] else: return [n] + rec2(n-1) print rec2(4) => [4,2,3,1] Thank you for the help! -- http://mail.python.org/mailman/listinfo/python-list
Re: Help- Recursion v. Iter Speed comparison
Heiko Wundram wrote: On Wednesday 02 March 2005 06:03, actuary77 wrote: It now makes sense if I write it, (simple): def rec2(n): if n == 0: return [] else: return [n] + rec2(n-1) Or, if you're not interested in a recursive function to do this job (which should be way faster...): def iter1(n): ... nl = range(1,n+1) ... nl.reverse() ... return nl ... print iter1(4) [4, 3, 2, 1] Recurse from time: 4.305942779541 seconds Iter from time: 0.009904632568359 seconds No comparison, why is recursion so slow? Would using a generator be faster than recursion? I really have complex list comprehension. I am interating n times. I have initial function: func(x) I have initial seed value: _aseed iteration value 1func(_aseed) 2func(func(_aseed)) n func(func(func...(_aseed)) What would be the fastest way to do this? -- http://mail.python.org/mailman/listinfo/python-list
Re: Question - What is a faster alternative to recursion?
Heiko Wundram wrote: On Wednesday 02 March 2005 06:03, actuary77 wrote: It now makes sense if I write it, (simple): def rec2(n): if n == 0: return [] else: return [n] + rec2(n-1) Or, if you're not interested in a recursive function to do this job (which should be way faster...): def iter1(n): ... nl = range(1,n+1) ... nl.reverse() ... return nl ... print iter1(4) [4, 3, 2, 1] Yes, iteration is 100 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.03 Is there a much faster way? -- http://mail.python.org/mailman/listinfo/python-list
Re: Help- Recursion v. Iter Speed comparison
Robert Kern wrote: actuary77 wrote: Recurse from time: 4.305942779541 seconds Iter from time: 0.009904632568359 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 1func(_aseed) 2func(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. I have a question on the generator solution. I have reviewed docs and I am unable to return a value from the generator. Below is a little speed comparison for a: 1. A recursive solution 2. A non-generator, list comprehension approach (Thank you) 3. The generator. Do you have any suggestions: ''' A comparison of Recursion, list comprehension and a generator ''' import sys from time import time sys.setrecursionlimit(1) cnt=1 # number of times to run each test # The parameters seed=10 n=100 def myfunc(x): return x + .5 # # A Recursive Approach # def rec(afunc,x,n): y = afunc(x) if n == 0: return y else: return rec(afunc,y,n-1) _b=time() for _i in range(0,cnt): _y = rec(myfunc,seed,n) _e=time() _t=_e-_b print "rec result: %r time: %f\n" % (_y,_t*1.) # # non-generator # def f1(afunc,aseed,n): values = [afunc(aseed)] for i in range(n-1): values.append(afunc(values[-1])) return values[-1] _b=time() for _i in range(0,100): _y = f1(myfunc,seed,n) _e=time() _t=_e-_b print "f1 result: %r time: %f\n" % (_y,_t*1.) # # generator # def f2(afunc,aseed,n): v = myfunc(aseed) print v for i in range(n): yield v v = afunc(v) def f2gen(i): for _i in range(1,n-1): f2(myfunc,seed,n) return f2(myfunc,seed,n) _b=time() for _i in range(0,cnt): _y = f2gen(_i) _e=time() _t=_e-_b print "f2gen result: %r time: %f\n" % (_y,_t*1.) ==> rec result: 10.0050488 time: 47669.999599 f1 result: 10.0049988 time: 399.999619 f2gen result: time: 30739.998817 I don't know how to get the generator to work correcly, I understand that the yield preserves the state of the funcion every time it is called. So in order to have myfunc called 50 times, the generator must be called 50 times, but it refuses to return a value. PEP 255 isn't helping me. Any further guidance would be greatly appreciated. -- http://mail.python.org/mailman/listinfo/python-list
Re: Help- Recursion v. Iter Speed comparison
Robert Kern wrote: actuary77 wrote: # # non-generator # def f1(afunc,aseed,n): values = [afunc(aseed)] for i in range(n-1): values.append(afunc(values[-1])) return values[-1] _b=time() for _i in range(0,100): _y = f1(myfunc,seed,n) Why do you do this? The whole point of this approach was to keep the intermediate results instead of recomputing them every time! The point is to get some meaningful results when "timing" the function. And why do you prepend underscores everywhere? It's bad Python style. I prepend underscore to differentiate local,private variables vs. global variables. Do not want to create a conflict. It is my understanding that this is the Python style for local v. global variables. _e=time() _t=_e-_b print "f1 result: %r time: %f\n" % (_y,_t*1.) # # generator # def f2(afunc,aseed,n): v = myfunc(aseed) print v for i in range(n): yield v v = afunc(v) def f2gen(i): for _i in range(1,n-1): f2(myfunc,seed,n) return f2(myfunc,seed,n) _b=time() for _i in range(0,cnt): _y = f2gen(_i) _e=time() _t=_e-_b print "f2gen result: %r time: %f\n" % (_y,_t*1.) ==> rec result: 10.0050488 time: 47669.999599 f1 result: 10.0049988 time: 399.999619 f2gen result: time: 30739.998817 I don't know how to get the generator to work correcly, I understand that the yield preserves the state of the funcion every time it is called. So in order to have myfunc called 50 times, the generator must be called 50 times, but it refuses to return a value. PEP 255 isn't helping me. No, the generator call creates a generator object which you iterate over. for value in f2(myfunc, seed, n): print value If you absolutely need a list: list(f2(myfunc, seed, n)) Thank you. -- http://mail.python.org/mailman/listinfo/python-list
