On May 15, 4:32 am, rusi rustompm...@gmail.com wrote:
On May 15, 2:19 am, Ian Kelly ian.g.ke...@gmail.com wrote:
Yup, linear. Assuming you optimize the even case so that it doesn't
actually call fib(n//2) twice, the call tree can be approximated as a
balanced binary tree with height
On May 15, 8:20 pm, Mark Dickinson dicki...@gmail.com wrote:
On May 15, 4:32 am, rusi rustompm...@gmail.com wrote:
On May 15, 2:19 am, Ian Kelly ian.g.ke...@gmail.com wrote:
Yup, linear. Assuming you optimize the even case so that it doesn't
actually call fib(n//2) twice, the call tree
On May 14, 2:48 am, Mark Dickinson dicki...@gmail.com wrote:
I don't see this (or Hans' version) as cheating at all.
Yeah sure -- cheating is a strong word :-)
This really *is* the power algorithm, just in a different number system from
the
usual one.
Yes that was my point. If we take
On Sat, May 14, 2011 at 11:24 AM, rusi rustompm...@gmail.com wrote:
def fib(n):
if n==1 or n==2:
return 1
elif even(n):
return sq(fib (n//2)) + 2 * fib(n//2) * fib(n//2 - 1)
else:
return sq(fib (n//2 + 1)) + sq(fib(n // 2))
This is a strange algo --
On May 15, 2:19 am, Ian Kelly ian.g.ke...@gmail.com wrote:
On Sat, May 14, 2011 at 11:24 AM, rusi rustompm...@gmail.com wrote:
def fib(n):
if n==1 or n==2:
return 1
elif even(n):
return sq(fib (n//2)) + 2 * fib(n//2) * fib(n//2 - 1)
else:
return sq(fib
On May 12, 3:06 am, Hans Mulder han...@xs4all.nl wrote:
On 03/05/2011 09:52, rusi wrote:
[If you believe it is, then try writing a log(n) fib iteratively :D ]
It took me a while, but this one seems to work:
from collections import namedtuple
Triple = namedtuple('Triple', 'hi mid lo')
On Fri, May 13, 2011 at 5:11 AM, rusi rustompm...@gmail.com wrote:
The tightest way I knew so far was this:
The 2x2 matrix
0 1
1 1
raised to the nth power gives the nth fibonacci number. [And then use
a logarithmic matrix mult]
Your version is probably tighter than this.
Oh, nice! I did
On 13/05/2011 13:11, rusi wrote:
On May 12, 3:06 am, Hans Mulderhan...@xs4all.nl wrote:
On 03/05/2011 09:52, rusi wrote:
[If you believe it is, then try writing a log(n) fib iteratively :D ]
It took me a while, but this one seems to work:
from collections import namedtuple
Triple =
On May 11, 11:06 pm, Hans Mulder han...@xs4all.nl wrote:
On 03/05/2011 09:52, rusi wrote:
[If you believe it is, then try writing a log(n) fib iteratively :D ]
It took me a while, but this one seems to work:
from collections import namedtuple
Triple = namedtuple('Triple', 'hi mid lo')
On 03/05/2011 09:52, rusi wrote:
[If you believe it is, then try writing a log(n) fib iteratively :D ]
It took me a while, but this one seems to work:
from collections import namedtuple
Triple = namedtuple('Triple', 'hi mid lo')
Triple.__mul__ = lambda self, other: Triple(
self.hi *
On Sun, 08 May 2011 01:44:13 -0400, Robert Brown wrote:
Steven D'Aprano steve+comp.lang.pyt...@pearwood.info writes:
If you value runtime efficiency over development time, sure. There are
plenty of languages which have made that decision: Pascal, C, Java,
Lisp, Forth, and many more.
I
* 2011-05-08T12:59:02Z * Steven D'Aprano wrote:
On Sun, 08 May 2011 01:44:13 -0400, Robert Brown wrote:
I don't understand why you place Lisp and Forth in the same category
as Pascal, C, and Java. Lisp and Forth generally have highly
interactive development environments, while the other
On Mon, May 9, 2011 at 2:34 AM, Teemu Likonen tliko...@iki.fi wrote:
But of course development time is a nicely vague concept. Depending on
the argument it can include just the features of language and
implementation. Other times it could include all the available resources
such as
Teemu Likonen tliko...@iki.fi writes:
* 2011-05-08T12:59:02Z * Steven D'Aprano wrote:
On Sun, 08 May 2011 01:44:13 -0400, Robert Brown wrote:
Python requires me to rewrite the slow bits of my program in C to get
good performance.
Python doesn't require you to re-write anything in C. If you
Steven D'Aprano steve+comp.lang.pyt...@pearwood.info writes:
If you value runtime efficiency over development time, sure. There are
plenty of languages which have made that decision: Pascal, C, Java,
Lisp, Forth, and many more.
I don't understand why you place Lisp and Forth in the same
On Mon, May 2, 2011 at 6:56 PM, Steven D'Aprano
steve+comp.lang.pyt...@pearwood.info wrote:
(The fact that most of those start with P is almost certainly a
coincidence.)
There's definitely something attractive about that letter. Lots of
programming languages' names start with P. I smell a
Chris Angelico wrote:
There's definitely something attractive about that letter. Lots of
programming languages' names start with P.
Including one I invented some years ago, that (in the spirit
of C and its derivatives) was called simply P.
(I was playing around with Sun's NeWS window server,
On 03 May 2011 00:21:45 GMT, Steven D'Aprano
steve+comp.lang.pyt...@pearwood.info wrote:
: Python aims at acceptable performance (between 10 and 100 times slower
: than C) and much easier development (between 10 and 100 times faster than
: C *wink*). If that tradeoff doesn't suit you,
On Tue, 3 May 2011 07:56:26 +1000, Chris Angelico
ros...@gmail.com wrote:
: often recursively. The compiler should generate code the way the CPU
: thinks (most optimally), i.e. iteratively.
:
: The CPU can function iteratively or recursively.
I should have said 'hardware' rather than CPU.
On May 3, 10:29 am, Chris Angelico ros...@gmail.com wrote:
On Tue, May 3, 2011 at 3:27 PM, Dan Stromberg drsali...@gmail.com wrote:
Doh.
Usually when someone gives a recursive solution to this problem, it's
O(logn), but not this time.
Here's a logn one:
:-) Ok so you beat me to it :D
I
On 01/-10/-28163 02:59 PM, rusi wrote:
On May 3, 10:29 am, Chris Angelicoros...@gmail.com wrote:
On Tue, May 3, 2011 at 3:27 PM, Dan Strombergdrsali...@gmail.com wrote:
Doh.
Usually when someone gives a recursive solution to this problem, it's
O(logn), but not this time.
Here's a logn
On May 3, 3:32 pm, Dave Angel da...@ieee.org wrote:
What I'm surprised at is that nobody has pointed out that the logn
version is also generally more accurate, given traditional floats.
Usually getting the answer accurate (given the constraints of finite
precision intermediates) is more
On Tue, May 3, 2011 at 8:32 PM, Dave Angel da...@ieee.org wrote:
What I'm surprised at is that nobody has pointed out that the logn version
is also generally more accurate, given traditional floats. Usually getting
the answer accurate (given the constraints of finite precision
intermediates)
On Tue, 03 May 2011 21:04:07 +1000, Chris Angelico wrote:
And that, Your Honour, is why I prefer bignums (especially for integers)
to floating point. Precision rather than performance.
I'm intrigued by your comment especially for integers, which implies
that you might use bignums for
On Tue, May 3, 2011 at 10:49 PM, Steven D'Aprano
steve+comp.lang.pyt...@pearwood.info wrote:
On Tue, 03 May 2011 21:04:07 +1000, Chris Angelico wrote:
And that, Your Honour, is why I prefer bignums (especially for integers)
to floating point. Precision rather than performance.
I'm intrigued
On Tue, May 3, 2011 at 5:49 AM, Steven D'Aprano
steve+comp.lang.pyt...@pearwood.info wrote:
On Tue, 03 May 2011 21:04:07 +1000, Chris Angelico wrote:
And that, Your Honour, is why I prefer bignums (especially for integers)
to floating point. Precision rather than performance.
I'm
Chris Angelico wrote:
The recursion is in the last block. Note that it calls a function,
then keeps going. It doesn't fork. There are two CALL_FUNCTION
opcodes, called*sequentially*. In terms of the call stack, there is
only ever one of those two calls active at any given time.
RuntimeError:
On Wed, May 4, 2011 at 3:10 AM, harrismh777 harrismh...@charter.net wrote:
If your point is that the infinite process is the problem, I agree. But my
point is that the cpu crunch and the rate at which the call stack is filled
has to do with the double call (which never finds tail processing).
On Tue, May 3, 2011 at 3:41 PM, Chris Angelico ros...@gmail.com wrote:
On Wed, May 4, 2011 at 3:10 AM, harrismh777 harrismh...@charter.net wrote:
If your point is that the infinite process is the problem, I agree. But my
point is that the cpu crunch and the rate at which the call stack is
On Wed, May 4, 2011 at 8:31 AM, Ian Kelly ian.g.ke...@gmail.com wrote:
A back-of-the-envelope calculation
shows that with modern technology it would take more than 10 ** 257
years to complete.
Then I propose that Python be extended to allow for underlying
hardware upgrades without terminating
On Mon, 2 May 2011 06:49:41 +1000, Chris Angelico
ros...@gmail.com wrote:
: Sure. Serialize this Python object in a way that can be given to, say, PHP:
: foo={asdf:qwer,zxcv:1234}; foo[self]=[1,2,3,foo]
: Recurse from self into the list, recurse from there into a
: dictionary... Okay, that's
On Mon, May 2, 2011 at 3:36 PM, Hans Georg Schaathun h...@schaathun.net wrote:
On Mon, 2 May 2011 06:49:41 +1000, Chris Angelico
ros...@gmail.com wrote:
: Sure. Serialize this Python object in a way that can be given to, say, PHP:
: foo={asdf:qwer,zxcv:1234}; foo[self]=[1,2,3,foo]
On Mon, May 2, 2011 at 4:28 PM, Chris Angelico ros...@gmail.com wrote:
reduce(`*,range(1,n+1))
reduce(`*,xrange(1,n+1))
Whoops, forgot which language I was using. Back-tick functions not
being available, these need to be:
reduce(operator.mul,range(1,n+1))
reduce(operator.mul,xrange(1,n+1))
On Apr 30, 11:14 am, Peter Otten __pete...@web.de wrote:
For the record, the one true way to implement the Fibonacci series in Python
is
def fib():
... a = b = 1
... while True:
... yield a
... a, b = b, a+b # look ma, no temporary variable
Not any claim
On Apr 30, 12:18 pm, Steven D'Aprano steve
+comp.lang.pyt...@pearwood.info wrote:
The number of calls is given by a recursive function with a similar form
as that of Fibonacci. As far as I know, it doesn't have a standard name,
but I'll call it R(n):
R(n) = R(n-1) + R(n-2) + 1, where R(0) =
On Mon, 02 May 2011 01:27:39 -0700, rusi wrote:
On Apr 30, 12:18 pm, Steven D'Aprano steve
+comp.lang.pyt...@pearwood.info wrote:
The number of calls is given by a recursive function with a similar
form as that of Fibonacci. As far as I know, it doesn't have a standard
name, but I'll call
On 02 May 2011 01:09:21 GMT, Steven D'Aprano
steve+comp.lang.pyt...@pearwood.info wrote:
: Ah, I see where you're coming from now! You think I'm arguing *against*
: the use of recursion. Not at all. Earlier in this thread, I said:
Fair enough. Somebody said something about recursion mainly
On 02 May 2011 08:56:57 GMT, Steven D'Aprano
steve+comp.lang.pyt...@pearwood.info wrote:
: I see your smiley, but there are a number of similar series as Fibonacci,
: with the same recurrence but different starting values, or similar but
: slightly different recurrences. E.g. Lucas,
On May 2, 2:53 pm, Hans Georg Schaathun h...@schaathun.net wrote:
On 02 May 2011 08:56:57 GMT, Steven D'Aprano
steve+comp.lang.pyt...@pearwood.info wrote:
: I see your smiley, but there are a number of similar series as Fibonacci,
: with the same recurrence but different starting values,
On 01/-10/-28163 02:59 PM, Chris Angelico wrote:
On Mon, May 2, 2011 at 3:36 PM, Hans Georg Schaathunh...@schaathun.net wrote:
On Mon, 2 May 2011 06:49:41 +1000, Chris Angelico
ros...@gmail.com wrote:
: Sure. Serialize this Python object in a way that can be given to, say, PHP:
:
On Sun, 01 May 2011 18:24:30 -0400, Terry Reedy
tjre...@udel.edu wrote:
: This does not make linear recursion 'bad', just impractical for general
: use on finite-memory machines. While I consider it very useful for
: learning, it is unnecessary because it is easy to write an iterative
:
On Mon, 02 May 2011 10:53:52 +0100, Hans Georg Schaathun wrote:
On 02 May 2011 08:56:57 GMT, Steven D'Aprano
steve+comp.lang.pyt...@pearwood.info wrote:
: I see your smiley, but there are a number of similar series as
Fibonacci, : with the same recurrence but different starting values, or
On Mon, 02 May 2011 14:14:20 +0100, Hans Georg Schaathun wrote:
On Sun, 01 May 2011 18:24:30 -0400, Terry Reedy
tjre...@udel.edu wrote:
: This does not make linear recursion 'bad', just impractical for
general : use on finite-memory machines. While I consider it very
useful for :
On 5/2/2011 9:14 AM, Hans Georg Schaathun wrote:
On Sun, 01 May 2011 18:24:30 -0400, Terry Reedy
: Python does not do this automatically because 1) it can be a semantic
: change under some circumstances; 2) one who wants the iterative version
: can just as easily write it directly;
That's
On 02 May 2011 16:41:37 GMT, Steven D'Aprano
steve+comp.lang.pyt...@pearwood.info wrote:
: You must be new to the Internet then :)
OK. Maybe I heard something worse last time I was an active news users,
years ago.
Anyway, most of the silly things I hear do not qualify as arguments :-)
:
On May 2, 5:24 pm, Steven D'Aprano steve
+comp.lang.pyt...@pearwood.info wrote:
As far as I'm concerned, there are only two definitions of Fibonacci
numbers that have widespread agreement in the mathematical community:
0,1,1,2,3 ... (starting from n=0)
1,1,2,3,5 ... (starting from n=1)
Any
Thomas Rachel wrote:
... because each recursion level 'return' calls fib() twice, and each of
those calls fib() twice, and you get the point...
yes - but they are called one after the other, so the twice call
counts only for execution speed, not for recursion depth.
def fib(n):
if n ==
On Mon, May 2, 2011 at 11:14 PM, Hans Georg Schaathun h...@schaathun.net
wrote:
That's the silliest argument I ever heard. The programmer should write
the code the way he and application domain experts think, i.e. very
often recursively. The compiler should generate code the way the CPU
On Tue, May 3, 2011 at 7:50 AM, harrismh777 harrismh...@charter.net wrote:
They *are not* called one after the other in the sense that there is ever
only one level of recursion with each call (not at all). Take a closer look.
Each call to fib() forces a double head, and each of those forces
On Mon, May 2, 2011 at 3:50 PM, harrismh777 harrismh...@charter.net wrote:
Thomas Rachel wrote:
... because each recursion level 'return' calls fib() twice, and each of
those calls fib() twice, and you get the point...
yes - but they are called one after the other, so the twice call
counts
On Tue, May 3, 2011 at 8:22 AM, Ian Kelly ian.g.ke...@gmail.com wrote:
They *are not* called one after the other in the sense that there is ever
only one level of recursion with each call (not at all). Take a closer look.
Each call to fib() forces a double head, and each of those forces another
On Mon, 02 May 2011 21:02:43 +0100, Hans Georg Schaathun wrote:
The other arguments are valid. And they make me lean more towards more
static, compiled languages without the excessive run-time dynamism of
python.
If you value runtime efficiency over development time, sure. There are
plenty
On May 3, 2:50 am, harrismh777 harrismh...@charter.net wrote:
The thing about this problem that puzzles me, is why we might consider
recursion for a possible solution in the first place
This can be answered directly but a bit lengthily.
Instead let me ask a seemingly unrelated (but actually
On Tue, May 3, 2011 at 11:48 AM, rusi rustompm...@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
On May 3, 5:21 am, Steven D'Aprano steve
+comp.lang.pyt...@pearwood.info wrote:
On Mon, 02 May 2011 21:02:43 +0100, Hans Georg Schaathun wrote:
The other arguments are valid. And they make me lean more towards more
static, compiled languages without the excessive run-time dynamism of
On Mon, May 2, 2011 at 7:13 PM, Chris Angelico ros...@gmail.com wrote:
On Tue, May 3, 2011 at 11:48 AM, rusi rustompm...@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
On Tue, May 3, 2011 at 3:27 PM, Dan Stromberg drsali...@gmail.com wrote:
But the recursive solution has time complexity of O(logn). The iterative
solution has time complexity of O(n). That's a significant difference for
large n - a significant benefit of the recursive version.
Are you sure?
On Mon, May 2, 2011 at 11:27 PM, Dan Stromberg drsali...@gmail.com wrote:
But the recursive solution has time complexity of O(logn). The iterative
solution has time complexity of O(n). That's a significant difference for
large n - a significant benefit of the recursive version.
It's linear
On Mon, May 2, 2011 at 10:29 PM, Chris Angelico ros...@gmail.com wrote:
On Tue, May 3, 2011 at 3:27 PM, Dan Stromberg drsali...@gmail.com wrote:
But the recursive solution has time complexity of O(logn). The iterative
solution has time complexity of O(n). That's a significant difference
On Sat, 30 Apr 2011 15:40:24 +0100, Paul Rudin
paul.nos...@rudin.co.uk wrote:
: Anytime you have enough data... there are plenty of things that are natural
to
: represent as recursive data structures, and often you don't know in
: advance how much data your code is going to have to deal
On Sun, 01 May 2011 09:18:36 +0100, Hans Georg Schaathun wrote:
On Sat, 30 Apr 2011 15:40:24 +0100, Paul Rudin
paul.nos...@rudin.co.uk wrote:
: Anytime you have enough data... there are plenty of things that are
natural to : represent as recursive data structures, and often you
don't
On 01 May 2011 09:04:27 GMT, Steven D'Aprano
steve+comp.lang.pyt...@pearwood.info wrote:
: Why? You might have 4000 MB of main memory, and only 2 MB (say?) of call
: stack allocated. The call stack can't grow indefinitely. If it does, you
: get a stack overflow:
Of course you do, but you
On Sun, 01 May 2011 10:27:14 +0100, Hans Georg Schaathun wrote:
On 01 May 2011 09:04:27 GMT, Steven D'Aprano
steve+comp.lang.pyt...@pearwood.info wrote:
: Why? You might have 4000 MB of main memory, and only 2 MB (say?) of
call : stack allocated. The call stack can't grow indefinitely. If
On 01 May 2011 11:56:57 GMT, Steven D'Aprano
steve+comp.lang.pyt...@pearwood.info wrote:
: Just google on stack overflow crash.
And I get loads of examples of stack overflows, but I could not see
anybody linking this to logically correct recursion. Wikipedia, for
instance, mentions two common
On Sun, May 1, 2011 at 11:15 PM, Hans Georg Schaathun h...@schaathun.net
wrote:
: The Python virtual machine knows how big each entry on the stack needs to
: be. (I don't, but it's got to be at least the size of a pointer.) So
: number of items is just a multiplication away from size of the
On 5/1/2011 5:27 AM, Hans Georg Schaathun wrote:
Of course you do, but you are still only saying that there might be
an application where this might happen because of excessive although
logically correct recursion. You have not given a single example where
it actually happened.
I will. Stack
Steven D'Aprano steve+comp.lang.pyt...@pearwood.info wrote in message
news:4dbbb7b6$0$29991$c3e8da3$54964...@news.astraweb.com...
On Sat, 30 Apr 2011 08:32:55 +0200, Peter Otten wrote:
harrismh777 wrote:
Ian Kelly wrote:
since the fact is that if
the function were properly coded, the call
On Sun, 01 May 2011 14:15:35 +0100, Hans Georg Schaathun wrote:
On 01 May 2011 11:56:57 GMT, Steven D'Aprano
steve+comp.lang.pyt...@pearwood.info wrote:
: Just google on stack overflow crash.
And I get loads of examples of stack overflows, but I could not see
anybody linking this to
On 5/1/2011 7:16 PM, BartC wrote:
Yes, it generates lots of calls.
About 22000 for fib(20), and 330 million for fib(40).
Using the standard double recursion implementation of fib, ncf(n)
(number of calls to fib() for fib(n)) requires ncf(n-2) + ncf(n+1) + 1
calls. The +1 is for the call to
On Fri, 29 Apr 2011 23:45:30 -0500, harrismh777
harrismh...@charter.net wrote:
: There is much debate about this generally, but general wisdom is that
: recursion is to be avoided when possible.
That is context dependent at best. You have given reasons to avoid
recursion in /executable
harrismh777 harrismh...@charter.net writes:
lalit wrote:
The above function return the
return (fib(n-1)+fib(n-2))
RuntimeError: maximum recursion depth exceeded in comparison
[36355 refs]
There is much debate about this generally, but general wisdom is that
recursion is to be avoided
harrismh777 wrote:
def fib(i=1):
a=1;n=1;l=[]
for j in range(0,i):
l.append(a)
p=a;a=n;n=p+a
Hm, did you run out of newlines?
return l
list=fib(7)
... and the above, is how I would actually code it
Nah, that can't be it ;)
For the
harrismh777 wrote:
Ian Kelly wrote:
since the fact is that if
the function were properly coded, the call stack for fib(20) would
never be more than 20 entries deep at any one time.
Not so much... and much more !
... because each recursion level 'return' calls fib() twice, and
On Sat, Apr 30, 2011 at 4:32 PM, Peter Otten __pete...@web.de wrote:
... because each recursion level 'return' calls fib() twice, and each
of those calls fib() twice, and you get the point...
I don't understand what you are trying to say -- but it's wrong ;)
Fortunately, most Python
On Sat, 30 Apr 2011 08:32:55 +0200, Peter Otten wrote:
harrismh777 wrote:
Ian Kelly wrote:
since the fact is that if
the function were properly coded, the call stack for fib(20) would
never be more than 20 entries deep at any one time.
Not so much... and much more !
...
Peter Otten wrote:
I don't understand what you are trying to say -- but it's wrong;)
... that was the point!:-))
--
http://mail.python.org/mailman/listinfo/python-list
Peter Otten wrote:
For the record, the one true way to implement the Fibonacci series in Python
is
def fib():
... a = b = 1
... while True:
... yield a
... a, b = b, a+b # look ma, no temporary variable
[snip]
I created two scripts, stressed them a bit,
Am 30.04.2011 09:43 schrieb harrismh777:
On the other hand, I am very much interested in yield, because of its
obvious persistent state, On the other hand, I don't like you fib()
function because it does not encapsulate the fib generator. I suppose
you are considering whatever module is holding
Am 30.04.2011 07:35, schrieb harrismh777:
Ian Kelly wrote:
since the fact is that if
the function were properly coded, the call stack for fib(20) would
never be more than 20 entries deep at any one time.
Not so much... and much more !
... because each recursion level 'return' calls fib()
On Sat, 30 Apr 2011 06:43:42 +0100, Paul Rudin
paul.nos...@rudin.co.uk wrote:
: Writing recurive code is acceptable and is a nice clear way of
: expressing things when you have naturally recursive data structures, and
: can lead to perfectly good compiled code. The problem in CPython is the
:
Hans Georg Schaathun h...@schaathun.net writes:
On Sat, 30 Apr 2011 06:43:42 +0100, Paul Rudin
paul.nos...@rudin.co.uk wrote:
: Writing recurive code is acceptable and is a nice clear way of
: expressing things when you have naturally recursive data structures, and
: can lead to
On Sat, 30 Apr 2011 12:29:00 +0100, Paul Rudin
paul.nos...@rudin.co.uk wrote:
: Clearly it makes a difference in any case where you'd hit the recursion
: limit.
What kind of problems make you hit the limit?
Other than when you forget the base case, I mean.
: It's no big deal to do
Hans Georg Schaathun h...@schaathun.net writes:
On Sat, 30 Apr 2011 12:29:00 +0100, Paul Rudin
paul.nos...@rudin.co.uk wrote:
: Clearly it makes a difference in any case where you'd hit the recursion
: limit.
What kind of problems make you hit the limit?
Other than when you forget the
harrismh777 wrote:
Peter Otten wrote:
For the record, the one true way to implement the Fibonacci series in
Python is
def fib():
... a = b = 1
... while True:
... yield a
... a, b = b, a+b # look ma, no temporary variable
[snip]
I created two
Thomas Rachel wrote:
You can have both with the following:
def fib(max=None):
a = b = 1
while max is None or a = max:
yield a
a, b = b, a+b
from itertools import islice
flist = list(islice(fib(), 10))
flist2 = list(fib(10))
Yes, yes, yes... but what
Peter Otten wrote:
But, this should also go to show you... that there is*never* just
one obvious way to do anything... contrary to the ZEN of Python...;-)
I take that as an indication that you are not Dutch;)
True enough... American Irish - mostly...
:-}
--
I tested your function. So You must remeber:
By definition, the first two Fibonacci numbers are 0 and 1, and each
subsequent number is the sum of the previous two. Some sources omit the
initial 0, instead beginning the sequence with two 1s.
In math terms it means: F(n) = F(n - 1) + F(n - 2)
I
import os
def fib(n):
if n == 1:
return(n)
else:
return (fib(n-1)+fib(n-2))
list=fib(20)
print(list)
The above function return the
return (fib(n-1)+fib(n-2))
RuntimeError: maximum recursion depth exceeded in comparison
[36355 refs]
can any one help
--
On 04/29/2011 08:22 PM, lalit wrote:
import os
def fib(n):
if n == 1:
return(n)
else:
return (fib(n-1)+fib(n-2))
list=fib(20)
print(list)
The above function return the
return (fib(n-1)+fib(n-2))
RuntimeError: maximum recursion depth exceeded in
import os
def fib(n):
if n == 1:
return(n)
else:
return (fib(n-1)+fib(n-2))
list=fib(20)
print(list)
The above function return the
return (fib(n-1)+fib(n-2))
RuntimeError: maximum recursion depth exceeded in comparison
[36355 refs]
can any one help
lalit wrote:
The above function return the
return (fib(n-1)+fib(n-2))
RuntimeError: maximum recursion depth exceeded in comparison
[36355 refs]
There is much debate about this generally, but general wisdom is that
recursion is to be avoided when possible. Another way to say this is,
Only
===begin==
def fib(i=1):
l=[]
p=0
a=1
n=p+a
for j in range(1,i+1):
l.append(a)
p=a
a=n
n=p+a
return l
list=fib(7)
===end==
... the above, if you want to return the
On Fri, Apr 29, 2011 at 9:57 PM, Jason Friedman ja...@powerpull.net wrote:
The first call to fib() recursively calls fib() twice. Each of those
will call fib() twice. Each of those will call fib() twice. Pretty
soon, you've got a lot of calls.
Which is hell for the running time, but doesn't
def fib(i=1):
a=1;n=1;l=[]
for j in range(0,i):
l.append(a)
p=a;a=n;n=p+a
return l
list=fib(7)
... and the above, is how I would actually code it
kind regards,
m harris
--
http://mail.python.org/mailman/listinfo/python-list
Ian Kelly wrote:
since the fact is that if
the function were properly coded, the call stack for fib(20) would
never be more than 20 entries deep at any one time.
Not so much... and much more !
... because each recursion level 'return' calls fib() twice, and each
of those calls fib()
95 matches
Mail list logo
