Fibonacci series recursion error

[lalit]

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

 

[Gary Herron]

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

 

[Jason Friedman]

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

 

[harrismh777]

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

 

[harrismh777]

===============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...

 

[Ian Kelly]

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.

 

[harrismh777]

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

 

[harrismh777]

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)

 

[Paul Rudin]

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

 

[Hans Georg Schaathun]

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.

 

[Peter Otten]

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
.... a = b = 1
.... while True:
.... yield a
.... a, b = b, a+b # look ma, no temporary variable
....[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,
4181, 6765]

 

[Peter Otten]

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

 

[Chris Angelico]

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

 

[Steven D'Aprano]

I don't understand what you are trying to say -- but it's wrong

I don't know what M Harris thinks he is trying to say either, but the
*naive* Fibonacci recursive algorithm is particularly badly performing
and should be avoided. It's ironic that of the two classic algorithms
used for teaching beginner programmers about recursion, neither is useful
in practice.

Except for fib(0) and fib(1), each call to fib() results in multiple
recursive calls. E.g. calling fib(4) results in the following sequence of
calls:

fib(4) # first call
=> fib(3) + fib(2) # three calls
=> fib(2) + fib(1) + fib(1) + fib(0) # seven calls
=> fib(1) + fib(0) + 1 + 1 + 0 # nine calls
=> 1 + 0 + 1 + 1 + 0 = 3

Thus requiring nine function calls to calculate fib(4) and a maximum
stack depth of four. As n increases, the number of calls increases at a
rate significantly faster than the Fibonacci sequence itself, making it
much worse than O(N**2) but not quite as bad as O(2**N):

n = 0 1 2 3 4 5 6 ... 35 ...
fib(n) = 0 1 1 2 3 5 8 ... 9227465 ...
calls = 1 1 3 5 9 15 25 ... 29860703 ...

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

Consequently, the naive recursive function is ridiculously slow and
memory-hungry.

This seems to have give rise to a myth that recursion should be avoided.
What needs to be avoided is *badly thought out* recursion. More sensible
recursive forms performs much better. I leave them as an exercise for
those who care, or an exercise in googling for those who care a little
less *wink*

 

[harrismh777]

I don't understand what you are trying to say -- but it's wrong

... that was the point! )

 

[harrismh777]

For the record, the one true way to implement the Fibonacci series in Python
is

... 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, and then timed:
I called the two scripts fib.py and fib2.py... here they are:

==================begin fib.py============================
#!/home/marcus/bin/python3
def fib():
a=b=1
while True:
yield a
a,b=b,a+b # look ma, no temporary variable

from itertools import islice
flist=list(islice(fib(), 100000))
==================end fib.py==============================


==================begin fib2.py===========================
#!/home/marcus/bin/python3
def fib(i=1):
a=b=1;l=[]
for j in range(0,i):
l.append(a)
a,b = b,a+b # look ma, I can do it too....
return l

list=fib(100000)
==================end fib2.py=============================

[ TIMES ] 1 core, 1.6 Ghz, 3196 bogomips

marcus@shire:~/Python3$ time ./fib.py

real 0m2.775s
user 0m1.908s
sys 0m0.820s


marcus@shire:~/Python3$ time ./fib2.py

real 0m2.796s
user 0m1.916s
sys 0m0.824s



You will notice first that the times are *almost* identical. So,
down under the heart of python, something is wrong. (never mind)

But the really interesting thing I found is that when I coded away
the temporary reference, 100ms of user time moved over to sys time. doh,
must be that 'somewhere' a 'temporary' reference had to be created...
and it doesn't look like it's optimized very well...

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


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 the fib() code as the
encapsulation, but I thought the idea from the OP was to create a
generator that could be called and return a list... this is a little goofy:
list(islice(fib(), X))

when what was wanted is:

list = fib(X)





kind regards,
m harris

 

[Thomas Rachel]

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 the fib() code as the
encapsulation, but I thought the idea from the OP was to create a
generator that could be called and return a list... this is a little goofy:
list(islice(fib(), X))

when what was wanted is:

list = fib(X)

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(), 100000))

flist2 = list(fib(100000))

or - if even the latter is unwanted -


def fibgen(max=None):
a = b = 1
while max is None or a <= max:
yield a
a, b = b, a+b

def fib(max=None, num=None):
if num is None:
return list(fibgen(max=max))
else:
from itertools import islice
return list(islice(fib(max=max), num))


Thomas

 

[Thomas Rachel]

Am 30.04.2011 07:35, schrieb harrismh777:

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

 

[Hans Georg Schaathun]

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

Well, if you run into a case where tail optimisation really makes a
difference, you probably want to reimplement it for a compiler that
guarantees tail optimisation, rather than reimplement it without
recursion within python.

 

[Paul Rudin]

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

Well, if you run into a case where tail optimisation really makes a
difference, you probably want to reimplement it for a compiler that
guarantees tail optimisation, rather than reimplement it without
recursion within python.

Clearly it makes a difference in any case where you'd hit the recursion
limit. It's no big deal to do your own unwinding of the recursion to a
loop, but the code is typically less clear.