Python: Fibonacci Sequence

Question

I'm just trying to improve my programming skill by making some basic functions.

I want to fill a list with fibonacci values, but I think my code gives the sum of all the numbers put together and prints that instead..

numberlist = []
i = 0
for i in range(20):
    numberlist.append(i)

print numberlist

fibonaccinumbers = []

for n in numberlist:
    def fib(n):
        a, b = 0, 1
        for i in range(n):
            a, b = b, a + b
        return a
    a = fib(n)
    fibonaccinumbers.append(a)


print a

Where have I gone wrong?

Solution 1

print a

Well, you print the final value.

---

Also some more comments on your code:

numberlist = []
i = 0
for i in range(20):
    numberlist.append(i)

You don’t need to initialize i there, the for loop does that for you. Also, you can simplify the whole block by just doing this:

numberlist = list(range(20))

And given that you don’t actually need that to be a list, you don’t need to construct that at all but you can just run for n in range(20) later.

Then you are redefinining your fib function inside the loop over and over again. You should define it outside of it and just reuse it.

Also, when you know you want to create a list of multiple fibonacci numbers, it helps to just store all the numbers you calculate in between. That way you don’t have to do the same things over and over again. You can also use a generator function to make that all easier:

def fibGenerator():
    a, b = 0, 1
    yield 0
    while True:
        a, b = b, a + b
        yield a

fibonaccinumbers = []
fib = fibGenerator()
for n in range(20):
    fibonaccinumbers.append(next(fib))

Instead of iterating over a range and calling next on the generator manually, you then can also just use the take-recipe from itertools to do it just like this:

fibonaccinumbers = take(20, fibGenerator())

On generators

Still not too sure what the generator does however.

A generator is a Python function which generates a sequence of return values. The values are generated lazily, that means when you request it. You create a generator by simply using yield instead of return. A yield will “return” a value and pause the generator. The next time you request a value, the generator will continue where it left off.

Using a generator allows you to create an endless sequence. As you see in the definition of fibGenerator above, there is a endless while-loop which has a yield inside. As the generator stops, it won’t hang up despite that loop.

Here is a quick self-explanationary example:

>>> def example():
    print('begin')
    i = 0
    while True:
        print('Calculating next value')
        yield i
        i += 1

>>> g = example()
>>> next(g)
begin
Calculating next value
0
>>> next(g)
Calculating next value
1
>>> next(g)
Calculating next value
2
>>> next(g)
Calculating next value
3
>>> next(g)
Calculating next value
4

The next function is the built-in function that requests the next value from the iterable. An iterable is anything you can iterate (e.g. for x in iterable: ...); and any generator is also an iterable.

Solution 2

The problem is on the last line. A distraction, I'm sure: you should be printing the list, not a.

Some other tips:

1: This whole block is just recreating the list returned by range:

numberlist = []
i = 0
for i in range(20):
    numberlist.append(i)

Assigning i = 0 is also moot. Instead, try:

numberlist = range(20)

In python 3, call list(range(20)), since range doesn't create a full-fledged list.

2: redefining the fib function on every pass of the loop won't create problems, but is surely not necessary. Move the definition outside :)

Solution 3

Sorry I'm being an idiot. I was printing 'a' which is the last iterated calculation of fibonacci..

I should have been printing my list instead.

Damn...

Solution 4

In the spirit of improving programming skills: you could use a generator and itertools.islice() to get the list of the first n fibonacci numbers:

from itertools import islice

def fib(a=0, b=1):
    yield a
    while True:
        yield b
        a, b = b, a + b

fibonacci_numbers = list(islice(fib(), 20))
print(fibonacci_numbers)

Output

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

Solution 5

Thought I would share some pyLove:

def fib(n, a = 0, b = 1):
    seq = [a,b]
    while len(seq) < n:
        seq += [seq[len(seq)-1] + seq[len(seq)-2]]
    return seq

print(fib(13))

output is:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]

or:

#or if you want to make up your own
print(fib(13, 1597, 2584))

output is:

[1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229]

View more solutions

Comments

[Justin]

It's still good you posted though. Suggestions: 1) Pull your function definition outside of the loop. 2) Range returns a list, so you can just say for n in range(20) instead of for n in numberlist and doing all that work in the beginning. 3) I recommend looking into list comprehensions, the second loop could look something like: fibonaccinumbers = [fib(n) for n in range(20)]

[poke]

@uʍopǝpısdn Hah, first! :P ^^

[Da Bx]

Whoops sorry guys, only just saw the last comments! I'll get right on it.

[Gort the Robot]

If you change it as @J.F. Sebastian recommends, it will run much faster. (Because it only runs through the loop in fib once.)

[Da Bx]

Gotcha, I'll see if I can do that.

[poke]

You might want to look at all the answers… Also please do not answer your own question just to add further questions but edit your question instead. See also the FAQ.

[Da Bx]

Ok sorry, thank you for all your help though. Still not too sure what the generator does however. I read the tip (stackoverflow.com/questions/102535/…)

[WyomingGeezer]

Best explanation of the yield statement I've seen. It fit right in with my experiments on Fibonacci numbers. Thank you!