Python Fibonacci Sequence

Summary: in this tutorial, you’ll learn how to define a custom Sequence type in Python and how to implement the Fibonacci sequence using a custom Sequence type.

Introduction to the custom Sequence type in Python

Sometimes, it’s useful to implement a custom sequence type that has functions similar to the built-in sequence type like tuples and lists.

As you’ve learned so far, a sequence can be mutable or immutable. In this tutorial, you’ll focus on defining a custom immutable sequence type.

Basically, an immutable sequence type should support two main functions:

• Return the number of elements of the sequence. Technically, this requirement is not necessary.
• Return an element at a given index or raise an IndexError if the index is out of bounds.

If an object can fullfil the above requirements, then you can:

• Use the square brackets [] syntax to retrieve an element by an index.
• Iterate over the elements of the sequence using the for loop, comprehension, etc.

Technically, a custom sequence type needs to implement the following methods:

• __getitem__ – returns an element at a given index.
• __len__ – returns the length of the sequence.

1) The __getitem__ method

The __getitem__ method has the index argument which is an integer. The ___getitem__ should return an element from the sequence based on the specified index.

The range of the index should be from zero to length - 1. If the index is out of bounds, the __getitem__ method should raise an IndexError exception.

Also, the __getitem__ method can accept a slice object to support slicing.

2) The __len__ method

If a custom sequence has the __len__ method, you can use the built-in len function to get the number of elements from the sequence.

Introduction to the Fibonacci sequence

The Fibonacci sequence was first discovered by Leonardo Fibonacci, who is an Italian mathematician, around A.D. 1170.

In the Fibonacci sequence, each number is the sum of two numbers that precede it. For example:

1, 1, 2, 3, 5, 8 , 13, 21, ...

The following formula describes the Fibonacci sequence:

f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2) if n > 2

Some sources state that the Fibonacci sequence starts at zero, not 1 like this:

0, 1, 1, 2, 3, 5, 8 , 13, 21, ...

But we’ll stick with the original Fibonacci sequence that starts at one.

To calculate a Fibonacci number in Python, you define a recursive function as follows:

def fib(n):
    if n < 2:
        return 1
    return fib(n-2) + fib(n-1) Code language: Python (python)

In this recursive function, the fib(1) and fib(2) always returns 1. And when n is greater than 2, the fib(n) = fib(n-2) – fib(n-1)

The following adds a statement at the beginning of the fib function for the logging debugging purpose:

def fib(n):
    print(f'Calculate Fibonacci of {n}')
    if n < 2:
        return 1
    return fib(n-2) + fib(n-1)Code language: Python (python)

And this shows output of the fib function when calculating the Fibonacci of 6:

Calculate the Fibonacci of 6
Calculate the Fibonacci of 4
Calculate the Fibonacci of 2
Calculate the Fibonacci of 0
Calculate the Fibonacci of 1
Calculate the Fibonacci of 3
Calculate the Fibonacci of 1
Calculate the Fibonacci of 2
Calculate the Fibonacci of 0
Calculate the Fibonacci of 1
Calculate the Fibonacci of 5
Calculate the Fibonacci of 3
Calculate the Fibonacci of 1
Calculate the Fibonacci of 2
Calculate the Fibonacci of 0
Calculate the Fibonacci of 1
Calculate the Fibonacci of 4
Calculate the Fibonacci of 2
Calculate the Fibonacci of 0
Calculate the Fibonacci of 1
Calculate the Fibonacci of 3
Calculate the Fibonacci of 1
Calculate the Fibonacci of 2
Calculate the Fibonacci of 0
Calculate the Fibonacci of 1

As shown clearly from the output, the fib function has many repetitions.

For example, it has to calculate the Fibonacci of 3 three times. This is not efficient.

To solve this, Python provides a decorator called lru_cache from the functools module.

The lru_cache allows you to cache the result of a function. When you pass the same argument to the function, the function just gets the result from the cache instead of recalculating it.

The following shows how to use the lru_cache decorator to speed up the fib function:

from functools import lru_cache


@lru_cache
def fib(n):
    print(f'Calculate the Fibonacci of {n}')
    if n < 2:
        return 1
    return fib(n-2) + fib(n-1)


fib(6)Code language: Python (python)

Output:

Calculate the Fibonacci of 6
Calculate the Fibonacci of 4
Calculate the Fibonacci of 2
Calculate the Fibonacci of 0
Calculate the Fibonacci of 1
Calculate the Fibonacci of 3
Calculate the Fibonacci of 5    

As shown clearly from the output, the number of calculations is reduced significantly.

Python Fibonacci sequence example

First, define a class that implements the Fibonacci sequence:

class Fibonacci:
    def __init__(self, n):
        self.n = nCode language: Python (python)

The __init__ method accepts an integer n that specifies the length of the sequence.

Second, define a static method that calculates a Fibonacci number of an integer:

@staticmethod
@lru_cache(2**16)
def fib(n):
    if n < 2:
        return 1
    return Fibonacci.fib(n-2) + Fibonacci.fib(n-1)Code language: Python (python)

Third, implement the __len__ method so that you can use the built-in len function to get the number of elements from the Fibonacci sequence:

def __len__(self):
    return self.n Code language: Python (python)

Finally, implement the __getitem__ method to support indexing through the square brackets syntax:

def __getitem__(self, index):
    if isinstance(index, int):
        if index < 0 or index > self.n - 1:
            raise IndexError

        return Fibonacci.fib(index)Code language: Python (python)

The __getitem__ method accepts an index which is an integer. The __getitem__ checks if the index is integer by using the isinstance function.

The __getitem__ method raises the IndexError exception if the index is out of bounds. Otherwise, it returns the Fibonacci number of the index.

Putting it all together.

from functools import lru_cache


class Fibonacci:
    def __init__(self, n):
        self.n = n

    def __len__(self):
        return self.n

    def __getitem__(self, index):
        if isinstance(index, int):
            if index < 0 or index > self.n - 1:
                raise IndexError

            return Fibonacci.fib(index)

    @staticmethod
    @lru_cache(2**16)
    def fib(n):
        if n < 2:
            return 1
        return Fibonacci.fib(n-2) + Fibonacci.fib(n-1)Code language: Python (python)

No, you can save the Fibonacci class in the fibonacci.py module and use it in a new script.

Using Fibonacci sequence

The following shows how to use the Fibonacci sequence from the fibonacci module:

from fibonacci import Fibonacci

fibonacci = Fibonacci(10)

# access elements via indices
print('Accessing Fibonacci sequence using []:')
print(fibonacci[0])
print(fibonacci[1])
print(fibonacci[2])

print('Accessing Fibonacci sequence using for loop:')
# using for loop
for f in fibonacci:
    print(f)Code language: Python (python)

Output:

Accessing Fibonacci sequence using []:
1
1
2
Accessing Fibonacci sequence using for loop:
1
1
2
3
5
8
13
21
34
55Code language: CSS (css)

How it works.

• First, create a new instance of the Fibonacci sequence that contains 10 elements.
• Second, access the Fibonacci sequence’s elements using the square brackets [].
• Third, use the Fibonacci sequence in a for loop.

Adding slicing support

To support slicing like this:

fibonacci[1:5]Code language: CSS (css)

…you need to add a logic to handle the slice object.

In the fibonacci[1:5], the index argument of the __getitem__ method is a slice object whose start is 1 and stop is 5.

And you can use the indices method of the slice object to get the indices of elements to return from the sequence:

indices = index.indices(self.n)Code language: Python (python)

The self.n is the length of the sequence that will be sliced. In this case, it’s the number of elements in the Fibonacci sequence.

To returns a list of Fibonacci from the slice, you can pass the indices to range function and use the list comprehension as follows:

[Fibonacci.fib(k) for k in range(*indices)]Code language: Python (python)

The following shows the new version of the Fibonacci sequence that supports slicing:

from functools import lru_cache


class Fibonacci:
    def __init__(self, n):
        self.n = n

    def __len__(self):
        return self.n

    def __getitem__(self, index):
        if isinstance(index, int):
            if index < 0 or index > self.n - 1:
                raise IndexError

            return Fibonacci.fib(index)
        else:
            indices = index.indices(self.n)
            return [Fibonacci.fib(k) for k in range(*indices)]

    @staticmethod
    @lru_cache
    def fib(n):
        if n < 2:
            return 1
        return Fibonacci.fib(n-2) + Fibonacci.fib(n-1)Code language: Python (python)

Now, you can slice the Fibonacci sequence as follows:

from fibonacci import Fibonacci

fibonacci = Fibonacci(10)
print(fibonacci[1:5])Code language: Python (python)

Output:

[1, 2, 3, 5]Code language: JSON / JSON with Comments (json)

Summary

• Implement the __len__ and __getitem__ method to define a custom sequence.
• The __getitem__ method need to returns an element based on a given index or raise an IndexError if the index is out of bounds.