Fibonacci sequence is one of the most popular interview questions. There are several ways to implement it with Python. Let's see how to do that.

# Fibonacci Sequence

The *Fibonacci Sequence* is the series of numbers:

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

The next number is found by adding up the two numbers before it.

- The 2 is found by adding the two numbers before it (1+1)
- The 3 is found by adding the two numbers before it (1+2),
- And the 5 is (2+3),
- and so on!

The rule of *Fibonacci Sequence* is

x(n) = x(n-1) + x(n-2)

where:

x(n) is term number "n"

x(n-1) is the previous term (n-1)

x(n-2) is the term before that (n-2)

*source* : https://www.mathsisfun.com/numbers/fibonacci-sequence.html

## Method 1 : With for loop

```
# using for loop
def fibonacci_loop(num):
if num == 0:
return 0
elif num == 1 or num == 2:
return 1
elif num > 2:
a = 1 # variable for (n - 1)
b = 1 # variable for (n - 2)
for _ in range(3, num + 1):
c = a + b
a, b = b, c
return c
```

```
%time fibonacci_loop(40)
CPU times: user 6 µs, sys: 0 ns, total: 6 µs
Wall time: 8.11 µs
102334155
```

## With recursion

We can solve the problem with for-loop, but it is not so intuitive.

From the rule of fibonacci sequence *x(n) = x(n-1) + x(n-2)* ,

we can make a function that call itself,

it is called *recursive* function.

```
# Recursive Method 1 : traditional recursive function
def fibonacci_recursion(num):
'''Return a fibonacci sequence value of num'''
if num == 0:
return 0
if num == 1 or num == 2:
return 1
return fibonacci_recursion(num - 2) + fibonacci_recursion(num - 1)
```

```
%time fibonacci_recursion(40)
CPU times: user 26.5 s, sys: 64 ms, total: 26.6 s
Wall time: 26.6 s
102334155
```

## Quiet slow??

It takes more and more time while the number is increased.

Because the function itself is needed to calculate same value over and over.

We can reduce total number of calling the function with saving the result to **cache**.

```
# Recursive Method 2 : With using explicit cache
cache = {}
def fibonacci_cache(num):
'''Return a fibonacci sequence value of num'''
if num in cache:
return cache[num]
if num == 0:
result = 0
elif num == 1 or num == 2:
result = 1
else:
result = fibonacci_cache(num - 2) + fibonacci_cache(num - 1)
cache[num] = result
return result
```

```
%time fibonacci_cache(40)
CPU times: user 2 µs, sys: 0 ns, total: 2 µs
Wall time: 5.01 µs
102334155
```

same result but super faster than normal recursive function

## Using LRU cache

Python provides a **functools** library helps the recursive function calls,

let's use Least Recently Used cache *(lru_cache)* from functools

```
# import library
from functools import lru_cache
```

```
# Recursive Method 3 : with implicit cache provided by functools
# set cache with 1000 (need to set a big values, small cache is NOT useful)
@lru_cache(maxsize = 1000)
def fibonacci(num):
'''Return a fibonacci sequence value of num'''
if num == 0:
return 0
if num == 1 or num == 2:
return 1
return fibonacci(num - 2) + fibonacci(num - 1)
```

```
%time fibonacci(40)
CPU times: user 3 µs, sys: 0 ns, total: 3 µs
Wall time: 5.25 µs
102334155
```

Little differ time values, but it could be ignored. (just some micro seconds)

## Conclusion

**We need to set lru_cache when using recursive function for performance**

## Discussion