How to implement Fibonacci series in python
The Fibonacci sequence is a series of numbers where each number is the sum of the two previous numbers. The first two numbers in the sequence are 0 and 1, and then each subsequent number is the sum of the two numbers before it. So, the first few numbers in the Fibonacci sequence are:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
If we notice, to get the Fibonacci number of n it’s the sum of Fibonacci number of n-1 and n-2
F(n) = F(n-1) + F(n-2)
We will look at 3 different methods to implement.
Method 1: python while loop
def fibonacci_loop(n: int) -> int:
# initialize 2 variables as 0, 1.
# which are intial values of a fibonacci series
n1, n2 = 0, 1
# now lets' loop through n-1 times
while n > 1:
# decrement the counter to stop the loop
n -= 1
# swap the value of n1 and n2 with n2 and n1+n2
n1, n2 = n2, n1 + n2
# variable n2 has the final result
return n2
Here we are using the while loop to iterate n-1 times. Also, we have 2 variables n1 and n2 to keep the values for each iteration. Now, let’s understand n1, n2 = n2, n1 + n2
As we discussed, Fibonacci series f(n) is f(n-1)+f(n-2) . Here n2 is our f(n). So for each iteration n2 keeps the sum of the previous iter. I am using multi-assignment to avoid creating temporary variables to keep the intermediate sum.
Following is a more generic algorithm using a temp variable to keep the temporary sum.
def fibonacci_loop(n: int) -> int:
n1 = 0
n2 = 1
count = 1
while count < n:
tmp = n1 + n2
n1 = n2
n2 = tmp
count += 1
return n2
Now let’s look at how to implement it using recursion.
Method 2: recursion
Let’s try to implement the formula f(n) = f(n-1) + f(n-2) using recursion.
def fibonacci_recur(n: int) -> int:
if n == 0:
return 0
if n <= 2:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
The results are the same by using either of the methods. Now the question is which method is better?
What’s better
Now that we implemented the program in 2 ways, let’s try to understand what’s better. To measure the performance of the code, I created the following function: (a very scientific way to test😉).
I am running the Fibonacci code starting from 1 to 39 to see how much time each function takes to evaluate. Following is the test code.
import time
def time_func():
max_n = 40
def run_func(func, n):
start = time.perf_counter()
result = func(i)
print(f"{func.__name__.ljust(15)}-> n={str(n).ljust(2)} {result=}, "
f"total time={time.perf_counter() - start:.8f} secs")
for i in range(1, max_n):
run_func(fibonacci_loop, i)
for i in range(1, max_n):
run_func(fibonacci_recur, i)
Let’s look at the results. First the loop method. The results are returned at a reasonable speed.
# using loop
fibonacci_loop -> n=1 result=1 total time=0.00000430 secs
fibonacci_loop -> n=2 result=1 total time=0.00000210 secs
fibonacci_loop -> n=3 result=2 total time=0.00000090 secs
fibonacci_loop -> n=4 result=3 total time=0.00000080 secs
fibonacci_loop -> n=5 result=5 total time=0.00000090 secs
fibonacci_loop -> n=6 result=8 total time=0.00000090 secs
fibonacci_loop -> n=7 result=13 total time=0.00000100 secs
fibonacci_loop -> n=8 result=21 total time=0.00000280 secs
fibonacci_loop -> n=9 result=34 total time=0.00000120 secs
fibonacci_loop -> n=10 result=55 total time=0.00000090 secs
fibonacci_loop -> n=11 result=89 total time=0.00000070 secs
fibonacci_loop -> n=12 result=144 total time=0.00000100 secs
fibonacci_loop -> n=13 result=233 total time=0.00000080 secs
fibonacci_loop -> n=14 result=377 total time=0.00000090 secs
fibonacci_loop -> n=15 result=610 total time=0.00000100 secs
fibonacci_loop -> n=16 result=987 total time=0.00000100 secs
fibonacci_loop -> n=17 result=1597 total time=0.00000100 secs
fibonacci_loop -> n=18 result=2584 total time=0.00000090 secs
fibonacci_loop -> n=19 result=4181 total time=0.00000110 secs
fibonacci_loop -> n=20 result=6765 total time=0.00000110 secs
fibonacci_loop -> n=21 result=10946 total time=0.00000110 secs
fibonacci_loop -> n=22 result=17711 total time=0.00000110 secs
fibonacci_loop -> n=23 result=28657 total time=0.00000110 secs
fibonacci_loop -> n=24 result=46368 total time=0.00000110 secs
fibonacci_loop -> n=25 result=75025 total time=0.00000110 secs
fibonacci_loop -> n=26 result=121393 total time=0.00000130 secs
fibonacci_loop -> n=27 result=196418 total time=0.00000120 secs
fibonacci_loop -> n=28 result=317811 total time=0.00000120 secs
fibonacci_loop -> n=29 result=514229 total time=0.00000120 secs
fibonacci_loop -> n=30 result=832040 total time=0.00000130 secs
fibonacci_loop -> n=31 result=1346269 total time=0.00000130 secs
fibonacci_loop -> n=32 result=2178309 total time=0.00000130 secs
fibonacci_loop -> n=33 result=3524578 total time=0.00000130 secs
fibonacci_loop -> n=34 result=5702887 total time=0.00000140 secs
fibonacci_loop -> n=35 result=9227465 total time=0.00000140 secs
fibonacci_loop -> n=36 result=14930352 total time=0.00000140 secs
fibonacci_loop -> n=37 result=24157817 total time=0.00000140 secs
fibonacci_loop -> n=38 result=39088169 total time=0.00000140 secs
fibonacci_loop -> n=39 result=63245986 total time=0.00000150 secs
Now let’s look at the recursion method performance.
fibonacci_recur-> n=1 result=1 total time=0.00000090 secs
fibonacci_recur-> n=2 result=1 total time=0.00000050 secs
fibonacci_recur-> n=3 result=2 total time=0.00000090 secs
fibonacci_recur-> n=4 result=3 total time=0.00000150 secs
fibonacci_recur-> n=5 result=5 total time=0.00000120 secs
fibonacci_recur-> n=6 result=8 total time=0.00000130 secs
fibonacci_recur-> n=7 result=13 total time=0.00000180 secs
fibonacci_recur-> n=8 result=21 total time=0.00000250 secs
fibonacci_recur-> n=9 result=34 total time=0.00000350 secs
fibonacci_recur-> n=10 result=55 total time=0.00000540 secs
fibonacci_recur-> n=11 result=89 total time=0.00000940 secs
fibonacci_recur-> n=12 result=144 total time=0.00001320 secs
fibonacci_recur-> n=13 result=233 total time=0.00002060 secs
fibonacci_recur-> n=14 result=377 total time=0.00003330 secs
fibonacci_recur-> n=15 result=610 total time=0.00005180 secs
fibonacci_recur-> n=16 result=987 total time=0.00008660 secs
fibonacci_recur-> n=17 result=1597 total time=0.00014050 secs
fibonacci_recur-> n=18 result=2584 total time=0.00022950 secs
fibonacci_recur-> n=19 result=4181 total time=0.00037390 secs
fibonacci_recur-> n=20 result=6765 total time=0.00063830 secs
fibonacci_recur-> n=21 result=10946 total time=0.00101400 secs
fibonacci_recur-> n=22 result=17711 total time=0.00141120 secs
fibonacci_recur-> n=23 result=28657 total time=0.00212920 secs
fibonacci_recur-> n=24 result=46368 total time=0.00352270 secs
fibonacci_recur-> n=25 result=75025 total time=0.00618250 secs
fibonacci_recur-> n=26 result=121393 total time=0.01017430 secs
fibonacci_recur-> n=27 result=196418 total time=0.01584420 secs
fibonacci_recur-> n=28 result=317811 total time=0.02798530 secs
fibonacci_recur-> n=29 result=514229 total time=0.04655380 secs
fibonacci_recur-> n=30 result=832040 total time=0.07358940 secs
fibonacci_recur-> n=31 result=1346269 total time=0.11667970 secs
fibonacci_recur-> n=32 result=2178309 total time=0.19072480 secs
fibonacci_recur-> n=33 result=3524578 total time=0.31605260 secs
fibonacci_recur-> n=34 result=5702887 total time=0.47243740 secs
fibonacci_recur-> n=35 result=9227465 total time=0.78889710 secs
fibonacci_recur-> n=36 result=14930352 total time=1.32147390 secs
fibonacci_recur-> n=37 result=24157817 total time=2.09678590 secs
fibonacci_recur-> n=38 result=39088169 total time=3.37948670 secs
fibonacci_recur-> n=39 result=63245986 total time=5.53867920 secs
The performance degraded exponentially with each iteration.
Why is the recursion slow?
Let’s look at the following image on how the Fibonacci number is calculated for n=5
First, the program tries to get the Fibonacci numbers of 4 and 3. But since f(4) and f(3) are not available f(4) will request for f(3) and f(2) and f(3) will request for f(2) and f(1). Our program returns a value only when it’s less than 2. Until 2 or 1 is part of the request, the recursion will go on. Hence if you take a larger number, there is a significant spike in total evaluation time.
So is recursion “bad”? Should we not write recursive functions?
Recursion can be considered bad in Python when there is a more optimal way to implement the same algorithm using iteration or the recursive use case has the potential to generate more than 1000 function calls on the call stack.
But I still want to use recursion for the Fibonacci series. Is there a way I can make this faster? What if F(n) value can be reused instead of evaluated for each f(n-1) and f(n-2) iteration.
That’s where a cache is going to help!
Let’s implement a program that will remember the last value and return it instead of creating another recursive call (in short a cache). We will take the help of a Python dictionary and create a decorator.
from functools import wraps
def dict_cache(func):
a_dict = {}
@wraps(func)
def wrapper(n):
if n in a_dict:
return a_dict[n]
r = func(n)
a_dict[n] = r
return r
return wrapper
Here I have imported from functools import wraps to get the functions name while logging. The function has a dictionary where I store the values for n for the first time and from the next call onwards the code checks if n exists and returns it instead of making the function call.
Now let’s add the decorator to the recursive function and measure the timing.
@dict_cache
def fibonacci_recur(n: int) -> int:
if n == 0:
return 0
if n <= 2:
return 1
return fibonacci_recur(n - 1) + fibonacci_recur(n - 2)
fibonacci_recur-> n=1 result=1 total time=0.00000160 secs
fibonacci_recur-> n=2 result=1 total time=0.00000080 secs
fibonacci_recur-> n=3 result=2 total time=0.00000140 secs
fibonacci_recur-> n=4 result=3 total time=0.00000160 secs
fibonacci_recur-> n=5 result=5 total time=0.00000120 secs
fibonacci_recur-> n=6 result=8 total time=0.00000110 secs
fibonacci_recur-> n=7 result=13 total time=0.00000090 secs
fibonacci_recur-> n=8 result=21 total time=0.00000160 secs
fibonacci_recur-> n=9 result=34 total time=0.00000090 secs
fibonacci_recur-> n=10 result=55 total time=0.00000080 secs
fibonacci_recur-> n=11 result=89 total time=0.00000330 secs
fibonacci_recur-> n=12 result=144 total time=0.00000080 secs
fibonacci_recur-> n=13 result=233 total time=0.00000070 secs
fibonacci_recur-> n=14 result=377 total time=0.00000070 secs
fibonacci_recur-> n=15 result=610 total time=0.00000060 secs
fibonacci_recur-> n=16 result=987 total time=0.00000070 secs
fibonacci_recur-> n=17 result=1597 total time=0.00000080 secs
fibonacci_recur-> n=18 result=2584 total time=0.00000070 secs
fibonacci_recur-> n=19 result=4181 total time=0.00000080 secs
fibonacci_recur-> n=20 result=6765 total time=0.00000070 secs
fibonacci_recur-> n=21 result=10946 total time=0.00000080 secs
fibonacci_recur-> n=22 result=17711 total time=0.00000140 secs
fibonacci_recur-> n=23 result=28657 total time=0.00000430 secs
fibonacci_recur-> n=24 result=46368 total time=0.00000110 secs
fibonacci_recur-> n=25 result=75025 total time=0.00000080 secs
fibonacci_recur-> n=26 result=121393 total time=0.00000120 secs
fibonacci_recur-> n=27 result=196418 total time=0.00000080 secs
fibonacci_recur-> n=28 result=317811 total time=0.00000070 secs
fibonacci_recur-> n=29 result=514229 total time=0.00000080 secs
fibonacci_recur-> n=30 result=832040 total time=0.00000070 secs
fibonacci_recur-> n=31 result=1346269 total time=0.00000070 secs
fibonacci_recur-> n=32 result=2178309 total time=0.00000070 secs
fibonacci_recur-> n=33 result=3524578 total time=0.00000070 secs
fibonacci_recur-> n=34 result=5702887 total time=0.00000070 secs
fibonacci_recur-> n=35 result=9227465 total time=0.00000080 secs
fibonacci_recur-> n=36 result=14930352 total time=0.00000080 secs
fibonacci_recur-> n=37 result=24157817 total time=0.00000080 secs
fibonacci_recur-> n=38 result=39088169 total time=0.00000080 secs
fibonacci_recur-> n=39 result=63245986 total time=0.00000080 secs
Now, that’s a significant improvement.
Is there any other way?
Yes, there is. Python’s functools library provides lru_cacheand cache methods that can be used to cache results.
lru_cache and cache are the same, except lru_cache allows you to define the maximum size for caching. Use them as per your project needs.
Learn about the LRU cache below:
Let’s use it in our Python code. (I have created a separate function fibonacci_lru so that we can measure the performance later, the algo is the same as fibonacci_recur
from functools import lru_cache
@lru_cache()
def fibonacci_lru(n: int) -> int:
if n == 0:
return 0
if n <= 2:
return 1
return fibonacci_lru(n-1)+fibonacci_lru(n-2)
Now let’s measure which one is better. I am using timeit and running the code 100,000 times to get the Fibonacci number for 100 and taking the average time.
import timeit
def time_it():
num = 100_000
total = timeit.timeit("fibonacci_lru(100)", globals=globals(), number=num)
print(f"fibonacci_lru -> {total=:.8f} average={total/num:.8f} secs")
total = timeit.timeit("fibonacci_loop(100)", globals=globals(), number=num)
print(f"fibonacci_loop -> {total=:.8f} average={total/num:.8f} secs")
total = timeit.timeit("fibonacci_recur(100)", globals=globals(), number=num)
print(f"fibonacci_recur-> {total=:.8f} average={total/num:.8f} secs")
All 3 methods are faster. Although both the caching methods seem to be faster than the loop. Here are the results:
fibonacci_lru -> total=0.00517680 average=0.00000005 secs
fibonacci_loop -> total=0.39864330 average=0.00000399 secs
fibonacci_recur-> total=0.00676110 average=0.00000007 secs
I would go with the lru_cache method as it's simple and less code.
Thank you for reading through the article. This is the first article that I have written ever and published. Please do share any feedback or improvements needed. 😊