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(n1) + fibonacci(n2)
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
 Solving Fibonacci using improved for loop
 Solving Fibonacci using while loop
 Solving Fibonacci using generator
 Solving Fibonacci using recursion and memoization
 Solving Fibonacci using tabulation
 3 fascinating facts about Fibonacci
Solving Fibonacci using for loop
def fib(n):
fibonacci = [0, 1]
if n>2:
for i in range(2, n+1):
next = fibonacci[i1] + fibonacci[i2]
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 == n1:
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(n1)+fib(n2)
return memo[n]
Solving Fibonacci using tabulation
def fib(n):
table = [0 for i in range(n+1)]
table[1] = 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
 Fibonacci day is November 23 for the first numbers in sequence: 1123
 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

Every 3rd Fibonacci number is a multiple of 2.
Every 4th Fibonacci number is a multiple of 3.
Every 5th Fibonacci number is a multiple of 5.
Every 6th Fibonacci number is a multiple of 8.