On May 15, 8:20 pm, Mark Dickinson wrote:
> On May 15, 4:32 am, rusi wrote:
>
> > On May 15, 2:19 am, Ian Kelly 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
On May 15, 4:32 am, rusi wrote:
> On May 15, 2:19 am, Ian Kelly 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 log(n). The total number of nodes in
> >
On May 15, 2:19 am, Ian Kelly wrote:
> On Sat, May 14, 2011 at 11:24 AM, rusi 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)
On Sat, May 14, 2011 at 11:24 AM, rusi 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 -- logarithmic because i
On May 14, 2:48 am, Mark Dickinson 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 the standard log
On May 11, 11:06 pm, Hans Mulder 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')
> Triple.
On 13/05/2011 13:11, rusi wrote:
On May 12, 3:06 am, Hans Mulder 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', '
On Fri, May 13, 2011 at 5:11 AM, rusi 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 it this way once
On May 12, 3:06 am, Hans Mulder 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')
> Triple._
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 * othe
Teemu Likonen 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 w
On Mon, May 9, 2011 at 2:34 AM, Teemu Likonen 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 documentation, librar
* 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 Sun, 08 May 2011 01:44:13 -0400, Robert Brown wrote:
> Steven D'Aprano 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 L
Steven D'Aprano 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 category as
Pascal, C, and Java. Lisp
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 Mon, May 2, 2011 at 6:56 PM, Steven D'Aprano
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 conspiracy. The
word "programming" has
On Wed, May 4, 2011 at 8:31 AM, Ian Kelly 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 a script. This will
On Tue, May 3, 2011 at 3:41 PM, Chris Angelico wrote:
> On Wed, May 4, 2011 at 3:10 AM, harrismh777 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
On Wed, May 4, 2011 at 3:10 AM, harrismh777 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).
The double call _does
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: ma
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'
On Tue, May 3, 2011 at 10:49 PM, Steven D'Aprano
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 by your comment "especially f
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 non-i
On Tue, May 3, 2011 at 8:32 PM, Dave Angel 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 impo
On May 3, 3:32 pm, Dave Angel 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 important than p
On 01/-10/-28163 02:59 PM, rusi wrote:
On May 3, 10:29 am, Chris Angelico wrote:
On Tue, May 3, 2011 at 3:27 PM, Dan Stromberg 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
On May 3, 10:29 am, Chris Angelico wrote:
> On Tue, May 3, 2011 at 3:27 PM, Dan Stromberg 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 was trying to arrive at an answer
On Tue, 3 May 2011 07:56:26 +1000, Chris Angelico
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. Iteratively it
On 03 May 2011 00:21:45 GMT, Steven D'Aprano
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, perhaps Python is not the
: language for
On Mon, May 2, 2011 at 10:29 PM, Chris Angelico wrote:
> On Tue, May 3, 2011 at 3:27 PM, Dan Stromberg 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 signifi
On Mon, May 2, 2011 at 11:27 PM, Dan Stromberg 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 as written. I th
On Tue, May 3, 2011 at 3:27 PM, Dan Stromberg 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? It will produce
On Mon, May 2, 2011 at 7:13 PM, Chris Angelico wrote:
> On Tue, May 3, 2011 at 11:48 AM, rusi 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
On May 3, 5:21 am, Steven D'Aprano 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
> > python.
>
> If you value runtime eff
On Tue, May 3, 2011 at 11:48 AM, rusi 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
On May 3, 2:50 am, harrismh777 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 much the same)
questi
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
plent
On Tue, May 3, 2011 at 8:22 AM, Ian Kelly 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
>> double head
On Mon, May 2, 2011 at 3:50 PM, harrismh777 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 only f
On Tue, May 3, 2011 at 7:50 AM, harrismh777 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
> double head (n
On Mon, May 2, 2011 at 11:14 PM, Hans Georg Schaathun
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
> thinks (most optim
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):
>>> i
On May 2, 5:24 pm, Steven D'Aprano 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 other definition is rather, sh
On 02 May 2011 16:41:37 GMT, Steven D'Aprano
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 :-)
: The problem is, once you include side-e
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 Mon, 02 May 2011 14:14:20 +0100, Hans Georg Schaathun wrote:
> On Sun, 01 May 2011 18:24:30 -0400, Terry Reedy
>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 un
On Mon, 02 May 2011 10:53:52 +0100, Hans Georg Schaathun wrote:
> On 02 May 2011 08:56:57 GMT, Steven D'Aprano
>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 differ
On Sun, 01 May 2011 18:24:30 -0400, Terry Reedy
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
: version. So called
On 01/-10/-28163 02:59 PM, Chris Angelico wrote:
On Mon, May 2, 2011 at 3:36 PM, Hans Georg Schaathun wrote:
On Mon, 2 May 2011 06:49:41 +1000, Chris Angelico
wrote:
: Sure. Serialize this Python object in a way that can be given to, say, PHP:
: foo=asdf":"qwer","zxcv":"1234"}; foo["self"
On May 2, 2:53 pm, Hans Georg Schaathun wrote:
> On 02 May 2011 08:56:57 GMT, Steven D'Aprano
> 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
On 02 May 2011 08:56:57 GMT, Steven D'Aprano
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, primefree, Pell, Padovan and
: Perrin numb
On 02 May 2011 01:09:21 GMT, Steven D'Aprano
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 being
a beginner's error. I don't th
On Mon, 02 May 2011 01:27:39 -0700, rusi wrote:
> On Apr 30, 12:18 pm, Steven D'Aprano +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 cal
On Apr 30, 12:18 pm, Steven D'Aprano 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) = R(1) = 1
Changing your definitio
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
On Mon, May 2, 2011 at 4:28 PM, Chris Angelico 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))
Chris Angelico
--
On Mon, May 2, 2011 at 3:36 PM, Hans Georg Schaathun wrote:
> On Mon, 2 May 2011 06:49:41 +1000, Chris Angelico
> 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]
>
> Wouldn't cyclic references
On Mon, 2 May 2011 06:49:41 +1000, Chris Angelico
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 a rath
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 Sun, 01 May 2011 14:15:35 +0100, Hans Georg Schaathun wrote:
> On 01 May 2011 11:56:57 GMT, Steven D'Aprano
>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. Wi
"Steven D'Aprano" 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 stack for fib(20) would
never be mor
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
On Sun, May 1, 2011 at 11:15 PM, Hans Georg Schaathun
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 items".
>
>
On 01 May 2011 11:56:57 GMT, Steven D'Aprano
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 causes, neither of which has anyth
On Sun, 01 May 2011 10:27:14 +0100, Hans Georg Schaathun wrote:
> On 01 May 2011 09:04:27 GMT, Steven D'Aprano
>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 ov
On 01 May 2011 09:04:27 GMT, Steven D'Aprano
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 are still only saying that there might
On Sun, 01 May 2011 09:18:36 +0100, Hans Georg Schaathun wrote:
> On Sat, 30 Apr 2011 15:40:24 +0100, Paul Rudin
>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
On Sat, 30 Apr 2011 15:40:24 +0100, Paul Rudin
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 with.
Sure, but one would t
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 di
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...
:-}
--
http://mail.pyth
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
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
Hans Georg Schaathun writes:
> On Sat, 30 Apr 2011 12:29:00 +0100, Paul Rudin
>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.
Anytime you h
On Sat, 30 Apr 2011 12:29:00 +0100, Paul Rudin
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 your own unwinding of th
Hans Georg Schaathun writes:
> On Sat, 30 Apr 2011 06:43:42 +0100, Paul Rudin
>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
On Sat, 30 Apr 2011 06:43:42 +0100, Paul Rudin
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
: lack of tail optimizat
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()
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 holdin
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,
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
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 !.
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 i
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()
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 i
harrismh777 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 when possible
On Fri, 29 Apr 2011 23:45:30 -0500, harrismh777
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 code/, but that's a compiler
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() tw
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
On Fri, Apr 29, 2011 at 9:57 PM, Jason Friedman 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 answer the quest
===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 lis
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 us
> 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]
>
>
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 comparison
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
--
http:
95 matches
Mail list logo
