Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #4515
| References | (2 earlier) <mailman.1011.1304141265.9059.python-list@python.org> <vcNup.5316$Du7.1273@newsfe04.iad> <ipgl8i$nbm$1@r03.glglgl.eu> <0HFvp.18698$vT3.2042@newsfe06.iad> <b025622c-68da-40fe-959e-3714f221e9c8@k3g2000prl.googlegroups.com> |
|---|---|
| Date | 2011-05-03 12:13 +1000 |
| Subject | Re: Recursion or iteration (was Fibonacci series recursion error) |
| From | Chris Angelico <rosuav@gmail.com> |
| Newsgroups | comp.lang.python |
| Message-ID | <mailman.1088.1304388800.9059.python-list@python.org> (permalink) |
On Tue, May 3, 2011 at 11:48 AM, rusi <rustompmody@gmail.com> wrote:
> What are their space/time complexities?
> Which do you prefer?
They're pretty similar actually. If you rework the first one to not
use range() but instead have a more classic C style of loop, they'll
be almost identical:
def powI(x,n):
result = 1
while n > 0:
result *= x
n-=1
return result
There's a subtle difference in that powR as you've coded it will
infinite-loop if given a negative exponent, while powI in any form
will simply return 1 (neither is technically correct, fwiw). Other
than that, the only difference is that one keeps its state on the call
stack, the other uses a temporary variable.
Performance would probably benefit from a special syntax meaning
"recurse", which would avoid the LOAD_GLOBAL for the function's name
(plus, things break if you pass recursive functions around after
compiling them - for instance, powR2=powR; def powR(x,n): os.exit() -
but if you do that, then you should expect to see nice bullet-holes in
your foot). However, I do not believe that Python would overall
benefit from any such thing.
Chris Angelico
Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Fibonacci series recursion error lalit <opposite800@gmail.com> - 2011-04-29 20:22 -0700
Re: Fibonacci series recursion error Gary Herron <gherron@islandtraining.com> - 2011-04-29 20:41 -0700
Re: Fibonacci series recursion error Jason Friedman <jason@powerpull.net> - 2011-04-30 03:57 +0000
Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-29 23:45 -0500
Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-29 23:51 -0500
Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-30 00:31 -0500
Re: Fibonacci series recursion error Peter Otten <__peter__@web.de> - 2011-04-30 08:14 +0200
Re: Fibonacci series recursion error rusi <rustompmody@gmail.com> - 2011-05-02 00:08 -0700
Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-04-30 06:50 +0100
Re: Fibonacci series recursion error Paul Rudin <paul.nospam@rudin.co.uk> - 2011-04-30 06:43 +0100
Re: Fibonacci series recursion error Ian Kelly <ian.g.kelly@gmail.com> - 2011-04-29 23:27 -0600
Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-30 00:35 -0500
Re: Fibonacci series recursion error Peter Otten <__peter__@web.de> - 2011-04-30 08:32 +0200
Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-04-30 16:37 +1000
Re: Fibonacci series recursion error Thomas Rachel <nutznetz-0c1b6768-bfa9-48d5-a470-7603bd3aa915@spamschutz.glglgl.de> - 2011-04-30 11:37 +0200
Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-05-02 16:50 -0500
Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-03 08:17 +1000
Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-05-03 12:10 -0500
Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-04 07:41 +1000
Re: Fibonacci series recursion error Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-03 16:31 -0600
Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-04 09:09 +1000
Re: Fibonacci series recursion error Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-02 16:22 -0600
Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-03 08:42 +1000
Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-02 18:48 -0700
Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 12:13 +1000
Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 15:29 +1000
Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-03 00:52 -0700
Re: Recursion or iteration (was Fibonacci series recursion error) Dave Angel <davea@ieee.org> - 2011-05-03 06:32 -0400
Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-03 03:51 -0700
Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 21:04 +1000
Re: Recursion or iteration (was Fibonacci series recursion error) Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-03 12:49 +0000
Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 23:02 +1000
Re: Recursion or iteration (was Fibonacci series recursion error) Hans Mulder <hansmu@xs4all.nl> - 2011-05-12 00:06 +0200
Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-13 04:11 -0700
Re: Recursion or iteration (was Fibonacci series recursion error) Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-13 07:55 -0600
Re: Recursion or iteration (was Fibonacci series recursion error) Hans Mulder <hansmu@xs4all.nl> - 2011-05-13 21:46 +0200
Re: Recursion or iteration (was Fibonacci series recursion error) Mark Dickinson <dickinsm@gmail.com> - 2011-05-13 14:48 -0700
Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-14 10:24 -0700
Re: Recursion or iteration (was Fibonacci series recursion error) Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-14 15:19 -0600
Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-14 20:32 -0700
Re: Recursion or iteration (was Fibonacci series recursion error) Mark Dickinson <dickinsm@gmail.com> - 2011-05-15 12:20 -0700
Re: Recursion or iteration (was Fibonacci series recursion error) Mark Dickinson <dickinsm@gmail.com> - 2011-05-15 12:29 -0700
Re: Recursion or iteration (was Fibonacci series recursion error) Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-02 23:46 -0600
csiph-web