How to write the Fibonacci Sequence?

Question

I had originally coded the program wrongly. Instead of returning the Fibonacci numbers between a range (ie. startNumber 1, endNumber 20 should = only those numbers between 1 & 20), I have written for the program to display all Fibonacci numbers between a range (ie. startNumber 1, endNumber 20 displays = First 20 Fibonacci numbers). I thought I had a sure-fire code. I also do not see why this is happening.

startNumber = int(raw_input("Enter the start number here "))
endNumber = int(raw_input("Enter the end number here "))

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

print map(fib, range(startNumber, endNumber))

Someone pointed out in my Part II (which was closed for being a duplicate - https://stackoverflow.com/questions/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii) that I need to pass the startNumber and endNumber through a generator using a while loop. Can someone please point me in the direction on how to do this? Any help is welcome.

---

I'm a learning programmer and I've run into a bit of a jumble. I am asked to write a program that will compute and display Fibonacci's Sequence by a user inputted start number and end number (ie. startNumber = 20 endNumber = 100 and it will display only the numbers between that range). The trick is to use it inclusively (which I do not know how to do in Python? - I'm assuming this means to use an inclusive range?).

What I have so far is no actual coding but rather:

• Write Fib sequence formula to infinite
• Display startNumber to endNumber only from Fib sequence.

I have no idea where to start and I am asking for ideas or insight into how to write this. I also have tried to write the Fib sequence forumla but I get lost on that as well.

Answer 1

Efficient Pythonic generator of the Fibonacci sequence

I found this question while trying to get the shortest Pythonic generation of this sequence (later realizing I had seen a similar one in a Python Enhancement Proposal), and I haven't noticed anyone else coming up with my specific solution (although the top answer gets close, but still less elegant), so here it is, with comments describing the first iteration, because I think that may help readers understand:

def fib():
    a, b = 0, 1
    while True:            # First iteration:
        yield a            # yield 0 to start with and then
        a, b = b, a + b    # a will now be 1, and b will also be 1, (0 + 1)

and usage:

for index, fibonacci_number in zip(range(10), fib()):
     print('{i:3}: {f:3}'.format(i=index, f=fibonacci_number))

prints:

  0:   0
  1:   1
  2:   1
  3:   2
  4:   3
  5:   5
  6:   8
  7:  13
  8:  21
  9:  34
 10:  55

(For attribution purposes, I recently noticed a similar implementation in the Python documentation on modules, even using the variables a and b, which I now recall having seen before writing this answer. But I think this answer demonstrates better usage of the language.)

Recursively defined implementation

The Online Encyclopedia of Integer Sequences defines the Fibonacci Sequence recursively as

F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1

Succinctly defining this recursively in Python can be done as follows:

def rec_fib(n):
    '''inefficient recursive function as defined, returns Fibonacci number'''
    if n > 1:
        return rec_fib(n-1) + rec_fib(n-2)
    return n

But this exact representation of the mathematical definition is incredibly inefficient for numbers much greater than 30, because each number being calculated must also calculate for every number below it. You can demonstrate how slow it is by using the following:

for i in range(40):
    print(i, rec_fib(i))

Memoized recursion for efficiency

It can be memoized to improve speed (this example takes advantage of the fact that a default keyword argument is the same object every time the function is called, but normally you wouldn't use a mutable default argument for exactly this reason):

def mem_fib(n, _cache={}):
    '''efficiently memoized recursive function, returns a Fibonacci number'''
    if n in _cache:
        return _cache[n]
    elif n > 1:
        return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
    return n

You'll find the memoized version is much faster, and will quickly exceed your maximum recursion depth before you can even think to get up for coffee. You can see how much faster it is visually by doing this:

for i in range(40):
    print(i, mem_fib(i))

(It may seem like we can just do the below, but it actually doesn't let us take advantage of the cache, because it calls itself before setdefault is called.)

def mem_fib(n, _cache={}):
    '''don't do this'''
    if n > 1:  
        return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
    return n

Recursively defined generator:

As I have been learning Haskell, I came across this implementation in Haskell:

fib@(0:tfib) = 0:1: zipWith (+) fib tfib

The closest I think I can get to this in Python at the moment is:

from itertools import tee

def fib():
    yield 0
    yield 1
    # tee required, else with two fib()'s algorithm becomes quadratic
    f, tf = tee(fib()) 
    next(tf)
    for a, b in zip(f, tf):
        yield a + b

This demonstrates it:

[f for _, f in zip(range(999), fib())]

It can only go up to the recursion limit, though. Usually, 1000, whereas the Haskell version can go up to the 100s of millions, although it uses all 8 GB of my laptop's memory to do so:

> length $ take 100000000 fib 
100000000

Answer 2

use recursion:

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
x=input('which fibonnaci do you want?')
print fib(x)

Answer 3

This is the simplest one in python for Fibonacci series but adjusted [0] in output array by append() to result in result list second variable that is result.append(second)

def fibo(num):
    first = 0
    second = 1
    result = [0]
    print('Fibonacci series is')
    for i in range(0,num):
        third = first + second
        #print(second)
        result.append(second)
        first = second
        second = third
    print(result)
    return
fibo(7)

OUTPUT

Fibonacci series is
[0, 1, 1, 2, 3, 5, 8, 13]

Answer 4

This was a practice assignment that I saw on Khan Academy's Sal on Python Programming: https://www.khanacademy.org/science/computer-science-subject/computer-science/v/exercise---write-a-fibonacci-function

He is probably not the first person to assign that as some work to do. But it is awesome figuring it out by yourself. I learned a lot figuring it out actually and it was a blast.

I recommend that you figure it out by yourself before you try and copy someone else's code for homework.

In the video above, Sal the instructor, shows shows the whole theory behind the Fibonacci number, and with that in mind you should be able to figure it out.

It took me about 10 minutes and this is the code I made (I am learning Python starting 3 days ago and this is my first programming language to learn). I would not have been able to write the code if it was not for the video from the tutorial before: https://www.khanacademy.org/science/computer-science-subject/computer-science/v/comparing-iterative-and-recursive-factorial-functions that one gives an example of Sal doing a recursive factorial equation and gives you the mind-set to solve this problem.

Here is my code:

def fibonacci(num):
    if num <= 1:          #base case
        return num
    else:
        return fibonacci(num-1) + fibonacci(num-2)

You can see that if the number is 1 or 0 then you just return the number.

I find this cleaner than saying if number is 1 return 1 and if number is 0 return 0.

Answer 5

Maybe this will help

def fibo(n):
    result = []
    a, b = 0, 1
    while b < n:
            result.append(b)
            a, b = b, b + a
    return result

Answer 6

there is a very easy method to realize that!

you can run this code online freely by using http://www.learnpython.org/

# Set the variable brian on line 3!

def fib(n):
"""This is documentation string for function. It'll be available by fib.__doc__()
Return a list containing the Fibonacci series up to n."""
result = []
a = 0
b = 1
while a < n:
    result.append(a)  # 0 1 1 2 3 5  8  (13) break
    tmp_var = b       # 1 1 2 3 5 8  13
    b = a + b         # 1 2 3 5 8 13 21
    a = tmp_var       # 1 1 2 3 5 8  13
    # print(a)
return result

print(fib(10))
# result should be this: [0, 1, 1, 2, 3, 5, 8]