Building a Fibonacci series in Python

[Sleepingforest]

I'm trying to build a Fibonacci series in Python 3.X for an assignment. I'm supposed to use lists and loops to get it to happen, and this is what I'm trying:

N = int (input ("Enter an integer: "))
fib = [0]*(N)
fib[0] = 1
fib[1] = 1
indexNum = 2
while N > 0:
fib[indexNum] = fib[indexNum - 1] + fib[indexNum - 2]
indexNum = int(indexNum + 1)
N = N - 1
print (fib)

When I run it through the module, it gives me an error (emphasis added):

Traceback (most recent call last):
File "C:\Users\Kyle\Documents\Homework\Python Class 2013\Week 3\Fibonacci.py", line 7, in <module>
fib[indexNum] = fib[indexNum - 1] + fib[indexNum - 2]
IndexError: list assignment index out of range

But if I simply type it out line by line in the module (without the loop part-- I enter it in manually) it works fine.

Anyone have some advice?

 

[mv2devnull]

I'm not familiar with Python. Does the "[0]*(N)" create a list of N items? How many items does your loop add? N? But you had two more to begin with.

Does the list have any "append" method?

 

[Sleepingforest]

The '[0]*N' part does indeed create a list with N terms; however, the part where I say fib[0] = 1 and fib[1] = 1 merely changes the value of those variables within the list (it doesn't add extra terms, as far as I know). So if 'N' were 5, I'd get a list of [1, 1, 0, 0, 0].

There should be an append method, but I haven't learned it yet. I just started learning programming, so my knowledge is pretty limited.

 

[douglasb]

I'm not really familiar with Python either, but I can tell you that this is a pretty easy one to solve.

Look the size of your array. Now look at where you start adding elements to your array, and look at how many times you go through the loop. See the problem?

Also, this might have been done more easily as a recursive method. See http://www.cs.northwestern.edu/academics/courses/110/html/fib_rec.html

 

[dighn]

you are looping N times, but you start with 2 items, so you get 2 + N items. you really want to loop N - 2 times

 

[Sleepingforest]

Ah, okay, now I see the problem. Thanks guys!

 

[Broheim]

I'm not really familiar with Python either, but I can tell you that this is a pretty easy one to solve.

Look the size of your array. Now look at where you start adding elements to your array, and look at how many times you go through the loop. See the problem?

Also, this might have been done more easily as a recursive method. See http://www.cs.northwestern.edu/academics/courses/110/html/fib_rec.html

this, fibonacci == recursive

 

[Cerb]

this, fibonacci == recursive

No, not that.

A recursive fibonacci sequence in Python can only be used for inputs that are lower than the recursion limit. fib(20) should work, but fib(5000) might not.

You can read here, for more details from the maker of Python, himself (not so much about the limitation, but that it exists because he doesn't understand that good recursive functions are the same as while loops, but with a lot less code than the equivalent explicit loop--IE, his statement about recursion is false for any function TCO can be applied to). There's a lot good about Python, but this alone would make me hate to use it for anything big (if I'm going to have to write 5-10x the code it would take, instead of using continuations, I might as well use a higher-performing language, instead--and, if you avoid globals, continuations can become quite natural to make, allow you modularize main loops, and tend to be very readable after-the-fact).

Unless you know your function will only recurse to a very shallow maximum depth, avoid recursion in Python. Instead, convert the problem into the equivalent while or for loop.

Trivial example, which will work to any depth with a language that supports TCO (because there won't be any depth to speak of):

>>> def rec (n):
...     if n <= 0:
...             return n
...     else:
...             return rec (n-1)
...
>>> rec(997)
0
>>> rec(998)
  File "<stdin>", line 5, in rec

The above line gets repeated enough to clear out the initial buffer contents (so, at least 298 times), and then ends with:

  File "<stdin>", line 2, in rec
RuntimeError: maximum recursion depth exceeded in comparison
>>>

It appears to be set to 1000. The last things you want are to (a) find out about this with real data manipulation, or (b) when you get marked down for not using loops to solve the problem 🙂.

 

[douglasb]

and that's why Python isn't a real language...