How to write the Fibonacci Sequence in Python

Question

Updated: EDIT! I have 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 - http://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.

Thank you.

---

---

Old: Hey there,

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.

Thank you for the help. I will be participating actively in this question and will appreciate ANY help.

Answer 1

Calculate the Fibonacci sequence from the beginning (presumably using a while loop), but don't output anything until the values are >= startNumber, and exit as soon as the values are greater than endNumber.

Actual code isn't provided because this smells like homework, but it sounds from your wording that bounding the output is the part that you were uncertain about.

Answer 2

You can get a good start point here:

• Fibonacci numbers (LiteratePrograms)

You have enough material there, a recursive approach, an iterative approach, the Binet's formula and some techniques for computing large individual Fibonacci numbers...

Answer 3

You must be joking or this is a homework problem? The Fibonacci function is discussed in the Python tutorial.

Answer 4

Start from reading good Python book. One of such book is "How to Think Like a Computer Scientist", especially chapter 5 in your case.

Answer 5

this was asked in general take a look

here is the python implementation

this is the question

Answer 6

The idea behind the Fibonacci sequence is shown in the following Python code:

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

This means that fib is a function that can do one of three things. It defines fib(1) == 1, fib(0) == 0, and fib(n) to be:

fib(n-1) + fib(n-2)

Where n is an arbitrary integer. This means that fib(2) for example, expands out to the following arithmetic:

fib(2) = fib(1) + fib(0)
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(2) = 1 + 0
fib(2) = 1

We can calculate fib(3) the same way with the arithmetic shown below:

fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
fib(2) = 1
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(3) = 1 + 1 + 0

The important thing to realize here is that fib(3) can't be calculated without calculating fib(2), which is calculated by knowing the definitions of fib(1) and fib(0). Having a function call itself like the fibonacci function does is called recursion, and it's an important topic in programming.

This sounds like a homework assignment so I'm not going to do the start/end part for you. Python is a wonderfully expressive language for this though, so this should make sense if you understand math, and will hopefully teach you about recursion. Good luck!

Edit: One potential criticism of my code is that it doesn't use the super-handy Python function yield, which makes the fib(n) function a lot shorter. My example is a little bit more generic though, since not a lot of languages outside Python actually have yield.

Answer 7

Go find out how to convert a recursive problem into an iterative one. Should be able to calculate from there.

That's might be the principles that they're trying to get you to learn, especially if this is an Algorithms course.

Answer 8

I think the most productive thing you can do will be to write some code. ANY code. If you can't get it to work, edit it into your original question along with the error you're getting, and we'll try to guide you toward getting that particular snippet of code to work. That should get you started.

Answer 9

There are lots of information about the Fibonacci Sequence on wikipedia and on wolfram. A lot more than you may need. Anyway it is a good thing to learn how to use these resource to find (quickly if possible) what you need.

Write Fib sequence formula to infinite

In math it's given in a recursive form:

In programming infinite doesn't exists. You can use a recursive form translating the math form directly in your language, for example in python it becomes:

def F(n):
    if n == 0: return 0
    elif n == 1: return 1
    else: return f(n-1)+f(n-2)

Try it in your favourite language and see this form requires a lot of memory as n gets bigger.

Go on on the sites I linked to you and will see this (on wolfram):

This one is pretty easy to implement and very, very fast to compute, in Python:

def F(n):
    return ((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))

An other way to do it is following the definition (from wikipedia):

The first number of the sequence is 0, the second number is 1, and each subsequent number is equal to the sum of the previous two numbers of the sequence itself, yielding the sequence 0, 1, 1, 2, 3, 5, 8, etc.

If your language supports iterators you may do something like:

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

Display startNumber to endNumber only from Fib sequence.

Once you know how to generate Fibonacci Numbers you just have to cycle trough the numbers and check if they verify the given conditions.

Suppose now you wrote a f(n) that returns the n-th term of the Fibonacci Sequence (like the one with sqrt(5) )

In most languages you can do something like:

def SubFib(startNumber, endNumber):
    n = 0
    cur = f(n)
    while cur<=endNumber:
        if startNumber <= cur:
            print cur
        n += 1
        cur = f(n)

In python I'd use the iterator form and go for:

def SubFib(startNumber, endNumber):
    for cur in F():
        if cur>endNumber: return
        if cur>=startNumber:
            yield cur

for i in SubFib(10, 200):
    print i

My hint is to learn to read what you need. Project Euler (google for it) will train you to do so :P Good luck and have fun!