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))``````