I have always thought of the Fibonacci sequence as a suitable challenge when learning a new programming language. According to Wikipedia “*the **Fibonacci numbers**, commonly denoted F*_{n}* form a sequence, called the **Fibonacci sequence**, such that each number is the sum of the two preceding ones, starting from 0 and 1*“. I posted my JavaScript solutions to solve the Fibonacci value for n where F_{n} = F_{n-1} + F_{n-2} here. In this post, I have taken a pass at a few possible Python solutions each with seed values F_{0} = 0 and F_{1} = 1.

The first obvious solution would be a **iterative** solution where the code follows the mathematical formula like:

```
def f(n: int) -> int:
"""Return the Fibonacci number for n by iterating over a list."""
result = [0, 1]
idx = 2
if n == 0: return 0
elif n == 1: return 1
else:
while idx < n:
result.append(result[idx - 1] + result[idx - 2])
idx += 1
return int(result[n - 1]) + int(result[n - 2])
```

This solution first generates the sequence up to n in a list and then calculates the value at index n. It works but not very efficient with large indices. We can, however, improve the efficiency of the code solution by eliminating the need to generate the sequence in order to calculate the value at index n. For example:

```
def f1(n: int) -> int:
"""Return the Fibonacci number for n by iteration."""
if n == 0:return 0
elif n == 1:return 1
else:
f0 = 0
f1 = 1
f2 = 1
for i in range (2, n):
fn = f1 + f2
f1 = f2
f2 = fn
return fn
```

```
def f2(n):
"""Return the Fibonacci number for n by recursion."""
if n == 0:return 0
elif n == 1:return 1
else:
fn = f2(n-1) + f2(n-2)
return fn
```

A recursive function is one where the function calls itself one or more times in its body. It is important to ensure that there is a way for a recursive function to terminate. Again, we see degradation with larger indices.

For the purposes of this post, I started to investigate the concept of memoization as implemented in Python. One possible way to memoize the recursive function could be:

```
def f3(n, _cache={}):
"""Return the Fibonacci number for n using a memoized recursive function"""
if n in _cache: return _cache[n]
elif n > 1:
return _cache.setdefault(n, f3(n-1) + f3(n-2))
return n
```

Memoization suits the Fibonacci problem adequately since you can store the results of calculations that you have done before and return a stored result rather than repeating the calculation. Performance is noticeably better at higher indices when compared to the previous solutions.