How to write the Fibonacci Sequence in Python

How to write the Fibonacci Sequence in Python

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

---

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 by Charles Duffy for How to write the Fibonacci Sequence in Python

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 by Micha Niklas for How to write the Fibonacci Sequence in Python

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 by James Thompson for How to write the Fibonacci Sequence in Python

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 by Calyth for How to write the Fibonacci Sequence in Python

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 by Andrea Ambu for How to write the Fibonacci Sequence in Python

There is 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 resources 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 exist. 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 that this form requires a lot of time as n gets bigger. In fact, this is O(2ⁿ) in time.

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:

from math import sqrt  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!

Answer by AlexB for How to write the Fibonacci Sequence in Python

def fib():      a,b = 1,1      num=eval(input("Please input what Fib number you want to be calculated: "))      num_int=int(num-2)      for i in range (num_int):          a,b=b,a+b      print(b)  

Answer by Jonas for How to write the Fibonacci Sequence in Python

15 minutes into a tutorial I used when learning Python, it asked the reader to write a program that would calculate a Fibonacci sequence from 3 input numbers (first Fibonacci number, second number, and number at which to stop the sequence). The tutorial had only covered variables, if/thens, and loops up to that point. No functions yet. I came up with the following code:

sum = 0  endingnumber = 1                    print "\n.:Fibonacci sequence:.\n"    firstnumber = input("Enter the first number: ")  secondnumber = input("Enter the second number: ")  endingnumber = input("Enter the number to stop at: ")    if secondnumber < firstnumber:        print "\nSecond number must be bigger than the first number!!!\n"    else:    while sum <= endingnumber:        print firstnumber        if secondnumber > endingnumber:            break        else:            print secondnumber          sum = firstnumber + secondnumber          firstnumber = sum          secondnumber = secondnumber + sum  

As you can see, it's really inefficient, but it DOES work.

Answer by user2095044 for How to write the Fibonacci Sequence in Python

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 by Filype for How to write the Fibonacci Sequence in Python

Just going through http://projecteuler.net/problem=2 this was my take on it

# Even Fibonacci numbers  # Problem 2    def get_fibonacci(size):      numbers = [1,2]      while size > len(numbers):          next_fibonacci = numbers[-1]+numbers[-2]          numbers.append(next_fibonacci)        print numbers    get_fibonacci(20)  

Answer by jdsantiagojr for How to write the Fibonacci Sequence in Python

def fib(x, y, n):      if n < 1:           return x, y, n      else:           return fib(y, x + y, n - 1)    print fib(0, 1, 4)  (3, 5, 0)    #  def fib(x, y, n):      if n > 1:          for item in fib(y, x + y, n - 1):              yield item      yield x, y, n    f = fib(0, 1, 12)  f.next()  (89, 144, 1)  f.next()[0]  55  

Answer by aaron-coding for How to write the Fibonacci Sequence in Python

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 by Timmy for How to write the Fibonacci Sequence in Python

These all look a bit more complicated than they need to be. My code is very simple and fast:

def fibonacci(x):        List = []      f = 1      List.append(f)      List.append(f) #because the fibonacci sequence has two 1's at first      while f<=x:          f = List[-1] + List[-2]   #says that f = the sum of the last two f's in the series          List.append(f)      else:          List.remove(List[-1])  #because the code lists the fibonacci number one past x. Not necessary, but defines the code better          for i in range(0, len(List)):          print List[i]  #prints it in series form instead of list form. Also not necessary  

Answer by DaVinci for How to write the Fibonacci Sequence in Python

Canonical Python code to print Fibonacci sequence:

a,b=1,1  while(True):    print a,    a,b=b,a+b       # Could also use b=a+b;a=b-a  

For the problem "Print the first Fibonacci number greater than 1000 digits long":

a,b=1,1  i=1  while(len(str(a))<=1000):    i=i+1    a,b=b,a+b    print i,len(str(a)),a  

Answer by sanooj for How to write the Fibonacci Sequence in Python

Another way of doing it:

a,n=[0,1],10  map(lambda i: reduce(lambda x,y: a.append(x+y),a[-2:]),range(n-2))  

Assigning list to 'a', assigning integer to 'n' Map and reduce are 2 of three most powerful functions in python. Here map is used just to iterate 'n-2' times. a[-2:] will get the last two elements of an array. a.append(x+y) will add the last two elements and will append to the array

Answer by Thomas Spycher for How to write the Fibonacci Sequence in Python

Why not just simply do the following?

x = [1,1]  for i in xrange(10):          x.append(x[-1] + x[-2])   print ', '.join(str(y) for y in x)  

Answer by Van Gogh for How to write the Fibonacci Sequence in Python

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 by Aaron Hall for How to write the Fibonacci Sequence in Python

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 enumerate(fib()):       print('{i:3}: {f:3}'.format(i=index, f=fibonacci_number))       if index == 10:           break  

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  

Answer by Akash Rana for How to write the Fibonacci Sequence in Python

Time complexity :

The caching feature reduces the normal way of calculating Fibonacci series from O(2^n) to O(n) by eliminating the repeats in the recursive tree of Fibonacci series :

Code :

import sys    table = [0]*1000    def FastFib(n):      if n<=1:          return n      else:          if(table[n-1]==0):              table[n-1] = FastFib(n-1)          if(table[n-2]==0):              table[n-2] = FastFib(n-2)          table[n] = table[n-1] + table[n-2]          return table[n]    def main():      print('Enter a number : ')      num = int(sys.stdin.readline())      print(FastFib(num))    if __name__=='__main__':      main()  

Answer by wadadaaa for How to write the Fibonacci Sequence in Python

Try this:

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

Answer by Kadmillos for How to write the Fibonacci Sequence in Python

based on classic fibonacci sequence and just for the sake of the one-liners

if you just need the number of the index, you can use the reduce (even if reduce it's not best suited for this it can be a good exercise)

def fibonacci(index):      return reduce(lambda r,v: r.append(r[-1]+r[-2]) or (r.pop(0) and 0) or r , xrange(index), [0, 1])[1]  

and to get the complete array just remove the or (r.pop(0) and 0)

reduce(lambda r,v: r.append(r[-1]+r[-2]) or r , xrange(last_index), [0, 1])