Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #4336 > unrolled thread

Fibonacci series recursion error

Back to article view | Back to comp.lang.python

Contents

  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

Page 1 of 3  [1] 2 3  Next page →

#4336 — Fibonacci series recursion error

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

[toc] | [next] | [standalone]

#4340

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
> [36355 refs]
>
> can any one help

You correctly test for n==1, but what about when n==2?    When the 
recursion works its way down to fib(2), you call both fib(1) and fib(0), 
but the latter starts an infinite sequence of calls to fib(-1), fib(-2) 
and so on without end.

Gary Herron

[toc] | [prev] | [next] | [standalone]

#4341

> 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

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.

Have a look at:  http://en.literateprograms.org/Fibonacci_numbers_(Python).

[toc] | [prev] | [next] | [standalone]

#4342

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 use recursion when there is no other obvious way to handle the 
problem".
Recursion is very tempting to young artists because its a ~cool trick, 
and because sometimes it requires very little coding (although huge 
amounts of memory!),  or as in your case, recursion depth errors.
Anyway, the better way to build a Fibonacci sequence generator is the 
following... I have expanded things a bit so that someone not knowing 
what the sequence is can see what is happening... you will notice simple 
'for' iterations, and no recursion:
===============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
     for j in l:
         print(j, end=' ')

fib(7)
=======================end======================


kind regards,

m harris

[toc] | [prev] | [next] | [standalone]

#4343

===============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 list, not print...

[toc] | [prev] | [next] | [standalone]

#4348

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

[toc] | [prev] | [next] | [standalone]

#4351

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 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
...
>>> from itertools import islice
>>> list(islice(fib(), 20))
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 
4181, 6765]

[toc] | [prev] | [next] | [standalone]

#4447

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 to 'the one true pythonic way' but fib can be written in
a clean recursive way with linear space-time behavior asz follows:

Dijkstra explained that fib is an 2nd order recurrence
-- fib(n) defined in terms of fib (n-1) and fib(n-2)
whereas programming loops and recursion are 1st order -- state at
iteration n defines state at iteration n+1.

Converting the 2nd order fib relation to a 1st order one trivially
gives a linear program.
The key insight from Dijkstra is that all we need to do is to move
from a recursive function returning fibonacci nos to one returning
pairs of adjacent ones.

def fibpair(n):
    # returns (fib(n), fib(n+1))
    if n==0:
        return (1,1)
    else:
        (a,b) = fibpair(n-1)
        return (b, a+b)

After that fib is just this:

def fib(n):
    a,b = fibpair(n)
    return a;

[toc] | [prev] | [next] | [standalone]

#4349

On Fri, 29 Apr 2011 23:45:30 -0500, harrismh777
  <harrismh777@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 code/, but that's a compiler issue.  You
have only given reason /for/ recursion in source code.  It generally
gives little and very reaadble code.  In almost every non-trivial
software project, the programmers will be more overworked than the
computer, and therefore they are the once to consider when optimising.

:  Recursion is very tempting to young artists because its a ~cool trick, 
:  and because sometimes it requires very little coding (although huge 
:  amounts of memory!),  or as in your case, recursion depth errors.

Waste of memory happens only with some types of recursion, and even
then it is usually negligible.  The recursion depth issue is the
result of a flawed base case, and nothing to do with a weakness of
recursion.

:  Anyway, the better way to build a Fibonacci sequence generator is the 
:  following... I have expanded things a bit so that someone not knowing 
:  what the sequence is can see what is happening... you will notice simple 
:  'for' iterations, and no recursion:

And surprisingly difficult to read for such a well-known operation as
Fibonacci numbers.  If you want to promote iteration, you had better
at least try to make it legible.

Your code is obviously more efficient in being O(n) whereas OP had
(I think) O(2^n), but that's not a property of iteration.  You can
make a recursive implementation which is O(n).  Any undergraduate 
textbook teaching recursion in any depth is likely to give it as an 
example; see e.g. Simon Thompson's Haskell book.

-- 
:-- Hans Georg

[toc] | [prev] | [next] | [standalone]

#4350

harrismh777 <harrismh777@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 when possible. Another way to say this is,
> "Only use recursion when there is no other obvious way to handle the
> problem".
> Recursion is very tempting to young artists because its a ~cool trick,
> and because sometimes it requires very little coding (although huge
> amounts of memory!),  


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 optimization, so it's not a good idea for python . Some
language standards guarantee tail optimization...

[toc] | [prev] | [next] | [standalone]

#4346

On Fri, Apr 29, 2011 at 9:57 PM, Jason Friedman <jason@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 answer the question of
why the maximum recursion depth is exceeded, 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.

The actual problem, as Gary pointed out, is that the base case is incomplete.

[toc] | [prev] | [next] | [standalone]

#4347

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() twice, and you get the point...


(not to mention, its not properly coded)

[toc] | [prev] | [next] | [standalone]

#4352

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 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 ;)

[toc] | [prev] | [next] | [standalone]

#4353

On Sat, Apr 30, 2011 at 4:32 PM, Peter Otten <__peter__@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 interpreters will not implement
double-tail-recursion as forking.

Chris Angelico

[toc] | [prev] | [next] | [standalone]

#4356

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() 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.


Thomas

[toc] | [prev] | [next] | [standalone]

#4502

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 == 1:
 >>>         return(n)
 >>>     else:
 >>>         return (fib(n-1)+fib(n-2))

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 (now four), and so on...  the recursion depth 
exception of the OP testifies against your theory.

The thing about this problem that puzzles me, is why we might consider 
recursion for a possible solution in the first place. In other words, 
normally we consider using recursion when we need information further 
down the stack then we have now... so that recursion is necessary 
because each head call will not have the information it needs for 
completion until the tail clean-up (coming back up the stack) provides 
that information.

In the case of the fib() numbers (or the fib sequence) recursion is not 
necessary for correctly handling of the problem. The simple 
straight-forward obvious way to handle the problem is to calculate the 
sequence outright in a straight-forward way. On the other hand, Otten's 
use of yield (making a generator) makes some sense too, in the case that 
we want to get the fib numbers over time without taking the time to 
calculate the entire sequence up-front.
Just saying...

kind regards,
m harris

[toc] | [prev] | [next] | [standalone]

#4505

On Tue, May 3, 2011 at 7:50 AM, harrismh777 <harrismh777@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 another
> double head (now four), and so on...  the recursion depth exception of the
> OP testifies against your theory.

def fib(n):
	if n==1:
		return n
	return fib(n-1)+fib(n-2)


dis.dis(fib)
  2           0 LOAD_FAST                0 (n)
              3 LOAD_CONST               1 (1)
              6 COMPARE_OP               2 (==)
              9 JUMP_IF_FALSE            5 (to 17)
             12 POP_TOP

  3          13 LOAD_FAST                0 (n)
             16 RETURN_VALUE
        >>   17 POP_TOP

  4          18 LOAD_GLOBAL              0 (fib)
             21 LOAD_FAST                0 (n)
             24 LOAD_CONST               1 (1)
             27 BINARY_SUBTRACT
             28 CALL_FUNCTION            1
             31 LOAD_GLOBAL              0 (fib)
             34 LOAD_FAST                0 (n)
             37 LOAD_CONST               2 (2)
             40 BINARY_SUBTRACT
             41 CALL_FUNCTION            1
             44 BINARY_ADD
             45 RETURN_VALUE

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. Also, as
earlier pointed out, the reason for the stack overflow is that fib(2)
will call fib(1) and fib(0), and fib(0) will call fib(-1) and fib(-2),
etc. Changing the operator from == to <= in the conditional return
will solve this.

Chris Angelico

[toc] | [prev] | [next] | [standalone]

#4557

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: maximum recursion depth exceeded in comparison
[36355 refs]

can any one help

[ @ Ian, Chris, Thomas ]

Thanks, guys, but I think y'all are still missing my point/question, as 
interesting as these discussions are... something is wrong (might be my 
understanding)...

... CPython must be making function calls by placing stack-frames on the 
call stack... which has a relatively small limit. Python does crappy 
tail optimization (one of the reasons to avoid recursion in Python) and 
yes, this is an infinite recursion... doh... but the main point for this 
part of the discussion is that the "maximum recursion depth exceeded in 
comparison" runtime error is posted because there are more stack-frames 
being posted to the call stack than there is call-stack to hold them! 
We might change this with sys.setrecursionlimit, but that's dangerous; 
but the bottom line is that in order for the recursion depth runtime 
error to be posted, somebody placed too many stack-frames on the call 
stack... in this case about 36,355 of them...   yes, the base-case is 
coded wrong and the process is infinite, the point is that tail 
processing doesn't even get to run... the silly thing pummels the call 
stack with stack-frames (obviously exceeding 20) and the runtime error 
is posted. 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).

What am I missing here>?

[toc] | [prev] | [next] | [standalone]

#4575

On Wed, May 4, 2011 at 3:10 AM, harrismh777 <harrismh777@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).

The double call _does not_ affect it. Failing to terminate recursion
_does_. I don't know what you mean by "cpu crunch" but the call stack
is going to get n entries. On the Python 2.6 on this system,
sys.getrecursionlimit() returns 1000, meaning that you can calculate
fib(1000) safely (okay, probably not quite as there'll be a few used
for other things, but fib(900) would be safe).

Chris Angelico

[toc] | [prev] | [next] | [standalone]

#4585

On Tue, May 3, 2011 at 3:41 PM, Chris Angelico <rosuav@gmail.com> wrote:
> On Wed, May 4, 2011 at 3:10 AM, harrismh777 <harrismh777@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).
>
> The double call _does not_ affect it. Failing to terminate recursion
> _does_. I don't know what you mean by "cpu crunch" but the call stack
> is going to get n entries. On the Python 2.6 on this system,
> sys.getrecursionlimit() returns 1000, meaning that you can calculate
> fib(1000) safely (okay, probably not quite as there'll be a few used
> for other things, but fib(900) would be safe).

Depends what you mean by "safe".  A back-of-the-envelope calculation
shows that with modern technology it would take more than 10 ** 257
years to complete.  That puts it well into the Dark Era of the
universe, long after the black holes will have decayed, when I suspect
it will be difficult to find a continued power source for the computer
to run.  And even if it somehow is still running, the process memory
will have been so thoroughly muddled by cosmic rays that the final
result of the calculation will be utterly worthless.

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.lang.python

csiph-web