Purfe

Learn, create and have fun with Python

# 6 ways to solve Fibonacci problem. Python

A Fibonacci sequence is a series of integers where the next number is found by adding up the two numbers before it

The formula can be visualised as follows

`fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)`

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Fibonacci sequence is generally used as an introduction to dynamic programming and recursion for Computer Science students and is a common interview question.

In this post we show 6 ways to solve Fibonacci sequence problem in Python. From simple loops to using tabulation.

Quick reference

### Solving Fibonacci using for loop

```    ```
def fib(n):
fibonacci = [0, 1]
if n>2:
for i in range(2, n+1):
next = fibonacci[i-1] + fibonacci[i-2]
fibonacci.append(next)
return fibonacci[n]
```
```

### Solving Fibonacci using improved for loop

Improved space complexity, more concise code

```    ```
def fib(n):
fib1 = fib2 = 1
for i in range(2, n):
fib1, fib2 = fib2, fib1 + fib2
return fib2
```
```

### Solving Fibonacci using while loop

```    ```
def fib(n):
previous, before_previous = 0, 1
i = 1
while i < n:
f_number = previous + before_previous
previous = before_previous
before_previous = f_number
i += 1
return f_number
```
```

### Solving Fibonacci using generator

Yielding Fibonacci using the generator and while loop. Creating Fibonacci ‘on demand’ utilizing `yield` to separate apparent computation from the actual one. It allows generating each new Fibonacci number as needed, rather than computing a long sequence.

```    ```
def gen_fib():
fib_1 = 1
fib_2 = 0
while True:
fib_next = fib_1 + fib_2
yield fib_next
fib_2 = fib_1
fib_1 = fib_next

def fib(n: int) -> int:
fib_n = gen_fib()
if n == 0:
return 0
elif n == 1:
return 1
for i in range(1, n):
if i == n-1:
return(fib_n.__next__())
else:
fib_n.__next__()
```
```

### Solving Fibonacci using recursion and memoization

```    ```
def fib(n: int, memo={}) -> int:
if n in memo.keys():
return memo[n]
if n <= 2:
return 1
else:
memo[n] = fib(n-1)+fib(n-2)
return memo[n]
```
```

### Solving Fibonacci using tabulation

```    ```
def fib(n):
table = [0 for i in range(n+1)]
table = 1
for count in range(n):
table[count+1] += table[count]
if count < len(table)-2:
table[count+2] += table[count]
return table[n]
```
```

### 3 fascinating facts about Fibonacci

1. Fibonacci day is November 23 for the first numbers in sequence: 1123
2. The ratio of consecutive Fibonacci numbers converges and approaches The Golden Ratio:

```        1 / 1 = 1
2 / 1 = 2
3 / 2 = 1.5
5 / 3 = 1.667
8 / 5 = 1.6
13 / 8 = 1.625
21 / 13 = 1.615
34 / 21 = 1.619
55 / 34 = 1.618
```
3. Every 3-rd Fibonacci number is a multiple of 2.

Every 4-th Fibonacci number is a multiple of 3.

Every 5-th Fibonacci number is a multiple of 5.

Every 6-th Fibonacci number is a multiple of 8.