Python Fibonacci Number Generator

Earlier I had mentioned I was taking several courses on computer science and algorithms while I was learning Python. The Fibonacci Sequence seems to appear a lot in these classes and I mentioned several assignments where I had to generate a list of Fibonacci numbers using a recursive function and Dynamic Programming. I talked about this in the article: Fibonacci Numbers - Tale of Two Algorithms using Python.

Although it was new to me when I was first learning it, generating Fibonacci numbers using a recursive function is unrealistic for large numbers. The instructor did not mention this in the computer science class. It wasn't until I tried to calculate the 100th Fibonacci number on my MacBook Pro in PyCharm using a recursive function and stared blankly at a non-responsive computer did I realize there may be a performance issue.

Later, in a separate algorithms course, a different instructor gave an introduction to the class and discussed the importance of algorithms. His introductory talk mentioned the naive recursive solution to generating large Fibonacci numbers and how it can be done much quicker using memoization, Dynamic Programming, etc. For me, this was the best example he could have given, because I had personally experienced the performance issue of the recursive algorithm.

Fibonacci Number Generator

Fast forward to yesterday when I was learning more about Python generators and generator expressions. As I learn these new techniques and features in Python, I like to apply them to previous learnings. It was then that I realized a Fibonacci number generator would be a great idea for generating Fibonacci numbers.

For the life of me, however, I couldn't come up with an elegant solution for a function to provide a sequence of the first n Fibonacci numbers. For example, if I wanted to print the first 20 Fibonacci numbers, I wanted the code to be as simple as follows, where fib is this magical Python generator I wanted to create to generate Fibonacci numbers.

for i in fib(20):
    print (i)

I came up with a solution, but it wasn't elegant. I took a peek on the Internet, and found a simple and elegant solution on StackOverflow. This is the elegant solution I had in mind.

def fib(n):
    a, b = 0, 1
    for _ in xrange(n):
        yield a
        a, b = b, a + b

This is obviously coded in Python 2.7 since it is using xrange. In Python 3, one can just use range.

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        yield a
        a, b = b, a + b

I had to document this new knowledge on my blog, because it is such an elegant solution for generating Fibonacci numbers. If you just want to use the Fibonacci numbers once, you can use it in a for loop as I mentioned above. If you want to store them for re-use, you can just add them to a list.

fibonacci_numbers = list(fib(20))
print fibonacci_numbers

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

range vs. xrange in Python 2.7

Since I mentioned range and xrange above, I thought I would mention the differences, if like me, you hadn't known about this before. This is something I just learned.

In Python 2.7, there is range and xrange. Range generates a list of numbers. It creates a list data structure in Python full of numbers. So, if you actually want a list of numbers, use range. If, on the otherhand, you are just iterating over a sequence of numbers, use xrange. Xrange returns an xrange object, which is an immutable iterable object ( not a generator ).

numbers = range(100) # list of numbers 0 - 99

for i in xrange(100): # immutable iterable object
    print i

In Python 3.x, there is only range and it works like xrange in Python 2.7.

Python Generators

While I am on the subject, I wanted to mention Python generators. A generator is any function that uses the yield keyword.

I can create a simple range-like generator that returns the first n number of integers starting with zero. Notice that this is not building a list of integers, but merely returning a sequence of integers to the client code one at a time as it creates them. This is the beauty of generators.

def my_range(n):
    loop_counter = 0
    number = 0

    while loop_counter < n:
        yield number
        number += 1
        loop_counter += 1

Just like with the Fibonacci number generator, I can iterate over the list of integers using a for loop or store them all in a list for re-use.

print my_range(10)
<generator object my_range at 0x101d544b0>

for i in my_range(10):
    print i

numbers = list(my_range(10))
print numbers
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Python generators can save a lot of memory, because they don't create a list of the numbers in this case. It just generates each number, one at a time, as you need it. This might not be a big deal for a small range of numbers, but for a really large range of numbers it is a big deal.

Posted by David Hayden
Koder Dojo
David Hayden is a professional Microsoft web developer. He mentors and tutors computer science students in C, C++, Java, and Python. In addition to writing computer science and programming tutorials at Koder Dojo, he also writes tutorials on C#, ASP.NET Core, and Azure as well as tutorials on Orchard Core.