This post has already been read 81 times!

Let’s explore recursion by writing a function to generate the terms of the Fibonacci sequence. We will use a technique called “memoization” to make the function fast.

We’ll first implement our own caching, but then we will use Python’s builtin memoization tool: the lru_cache decorator.

Fibonacci with Python
# Fibonacci Sequence
# 0,1,1,2,3,5,8,13,21


def fibonacci(n):
    if n < 0:
        raise ValueError('invalid input')
    if n == 0:
        return 0
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n > 2:
        return fibonacci(n - 1) + fibonacci(n - 2)


for n in range(0, 11):
    print(n, ":", fibonacci(n))
Fibonacci with Caching system in Python
# Cache values
fibonacci_cache = {}


def fibonacci2(n):
    # if we have cached the value, then return it
    if n in fibonacci_cache:
        return fibonacci_cache[n]

    # compute the nth term
    if n == 1:
        value = 1
    elif n == 2:
        value = 1
    elif n > 2:
        value = fibonacci2(n - 1) + fibonacci2(n - 2)

    # cache the value and return it
    fibonacci_cache[n] = value

    return value


# warning! the next loop is slow without caching
for n in range(1, 1001):
    print(n, ":", fibonacci2(n))
Fibonacci with cache system lru_cache in Python
from functools import lru_cache


@lru_cache(maxsize=1000)
def fibonacci3(n):
    # check that the input is a positive integer
    if type(n) != int:
        raise TypeError("n must be a positive integer")
    if n < 1:
        raise ValueError("n must be a positive integer")

    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n > 2:
        return fibonacci3(n - 1) + fibonacci3(n - 2)

for n in range(1, 1001):
    print(n, ":", fibonacci3(n))

 

 

Leave a Reply

Post Navigation