Fibonnaci 2 ways

# Fibonnaci 2 ways

## What is a Fibonnaci number?

Before we dive into the different methods, let's just review what a Fibonnaci number is. If you already know this, feel free to skip on to the next section.

You've likely seen the sequence before, it goes like this:
$$1, 1, 2, 3, 5, 8, 13, 21, 34, ...$$
Where each number is the sum of the previous 2 numbers (if the previous 2 numbers don't exist because you're too close to the start, they are zero).

So, positions 1 and 2 have the value 1.
Position 3 is then the values at positions 1 and 2 added together, which gives 2.
Position 4 is the values at position 2 and 3 added together, giving 3.

You get the picture.

So ... how would we write a function to give us the nth Fibonnaci number?

## Looping

The obvious way to solve this might be to simply loop around, calculating all the fibbonaci numbers until you get up to the one you want.

def get_nth_fibonaaci_loop(n):
prev = [1, 1]
for pos in range(3, n+1):
new = sum(prev)
prev[0] = prev[1]
prev[1] = new

return prev[1]


Let's walk through this to see exactly what it's doing...

##### prev = [1, 1]

This is initialising the first two values that we know to be 1. Everything else can be calculated just because we know these.

##### for pos in range(3, n+1):

We loop over all the values from 3 to n inclusive. We start from the 3rd position, because we have the first two values already (prev).

The end value for range is non inclusive, and so should always be one more than you want to count to. range(10) will count to 9 for example. To count to 10, use range(11).

##### new = sum(prev)

The nth (where n = pos in this loop) Fibonnaci number is the sum of the two previous numbers. prev always holds the two previous numbers, so just sum the list.

##### prev[0] = prev[1]

prev[1] = new
This shuffles the list back, adding the new value at the end, so that prev still represents the most recent two values.

##### return prev[1]

Once the loop finishes, the result to return is then the last value in the list (position 1).

Note that list positions start at 0, so the list above has 2 values at positions 0 and 1. This is common for lists and arrays in many programming languages.

## Recursive

Recursion is a concept often used in programming. Mostly, we can reduce the definition of "recursion" to "a function that calls itself". This may be overly simplistic, but it will do for our purposes.

If you read pretty much any blog post on recursion within coding, my guess is the author will use the Fibonnaci sequence to illustrate it. So, how would we implement the same function as above, only using recursion instead of that loop?

def get_nth_fibbonaci_recursive(n):
if n < 3:
return 1
return get_nth_fibbonaci_recursive(n-1) + get_nth_fibbonaci_recursive(n-2)


Let's walk through this one too, and clarify what is going on:

##### if n < 3: return 1

If the function is called for any value less than 3, it will return 1 (again, this is incorrect for zero and negative values, but this is for demonstration purposes, so we won't worry about that right now!)

For any recursive function, we always need to have at least one base case where the function will not call itself. Failure to add a case like this will mean the recursion never ends.

##### return get_nth_fibbonaci_recursive(n-1) + get_nth_fibbonaci_recursive(n-2)

For values of n that are 3 and above, we use this recursive formula to add together the two previous values in the sequence. These two values are then calculated by the same function, hence recursive.

## Performance

So there are (at least) 2 ways of writing a function to calculate Fibonnaci numbers. Is one of them better than the other? Or doesn't it matter?

Well, let's take a look at the code. The recursive function is significantly shorter and - if you ask me at least, you may have other opinions - it's easier to understand. It clearly lays out that the nth Fibbonaci number is the (n-1)th Fibonnaci number and the (n-2)th Fibonnaci number added together.

Great! So the recursive method is better then?

Not so fast ...

Let's take a look and see how long they take to run.

#### Fibonnaci loop performance

In [5]: import timeit

In [6]: def test_loop(n):
...:     for i in range(n+1):
...:         get_nth_fibonaaci_loop(i)

In [7]: timeit.timeit(lambda: test_loop(3))
Out[7]: 1.0851218000007066

In [8]: timeit.timeit(lambda: test_loop(10))
Out[8]: 6.122315000000526

In [9]: timeit.timeit(lambda: test_loop(100))
Out[9]: 607.2568042000003


Python provides a handy little library called timeit that can be used to time how long it takes to do something. We may cover this in more detail in a future post on performance measurement and improvement.

This is what I ran to test the performance of the loop function. I created a test_loop to call the get_nth_fibonnaci_loop function a specified number of times, incrementing the value of n to pass in each time.

Passing 3 to this loop would run the function 4 times, for the values 0, 1, 2, and 3. 0 is actually an edge case here, and our function will return the wrong result, because we haven't accounted for values of n less than 1. But this is more for demo purposes, so let's not worry about it. In the "real" world we would probably add some extra checks to validate the values passed to the function.

So running it 4 times, for trivial values took ~1 second. Running it 11 times took ~6 seconds, and running it 101 times took ~600 seconds.

Not bad actually. It looks as though we're talking roughly 10 iterations in 6 seconds, taking a little longer the higher the number we need to calculate.

How an algorithm performs (i.e. how much work it has to do) is often described using Big O notation. This is definitely something we will cover in a later post.

#### Recursive Fibbonaci performance

In [10]: def test_loop2(n):
...:     for i in range(n+1):
...:         get_nth_fibbonaci_recursive(i)

In [11]: timeit.timeit(lambda: test_loop2(3))
Out[11]: 0.5744964000041364

In [12]: timeit.timeit(lambda: test_loop2(10))
Out[12]: 19.45970269999816

In [13]: timeit.timeit(lambda: test_loop2(20))
Out[13]: 4240.980084800001


Note the final test here is 20 and not 100 - there's a reason for this: I had to kill the test for 100 because it was just running too long. 4240 seconds == 1 hour and 10 minutes: a bit of a difference from the loop going all the way up to the 100th Fibonnaci number in just over 10 minutes!

So, that's not good, right? Recursion was so much neater, so why is it taking so long? Even just getting just the 20th Fibonnaci number takes over 22 minutes!

In [14]: timeit.timeit(lambda: get_nth_fibbonaci_recursive(20))
Out[14]: 1385.3404860999872


Well, the reason is becuase this recursive approach is doing everything multiple times, and the higher the number you're calculating, the more often it re-calculates the lower numbers.

For example, let's calulate get_nth_fibbonaci_recursive(5)

get_nth_fibbonaci_recursive(5)
= get_nth_fibbonaci_recursive(4) + get_nth_fibbonaci_recursive(3)
= (get_nth_fibbonaci_recursive(3) + get_nth_fibbonaci_recursive(2)) + (get_nth_fibbonaci_recursive(2) + get_nth_fibbonaci_recursive(1))
= ((get_nth_fibbonaci_recursive(2) + get_nth_fibbonaci_recursive(1)) + 1) + (1 + 1)
= ((1 + 1) + 1) + (1 + 1)
= 5


As you can see, the function calls itself with the same values multiple times:

Call with value Number of calls
4 1
3 2
2 3
1 2

Plus the original call for 5, of course. That's 9 calls to the same function to calculate this, 4 of which are repetetive. If we run the function for 6 then it begins by calling itself for both 5 and 4, meaning we get these 9 calls, plus all calls needed to calculate the 4th Fibonnaci number. As the value for n gets higher, the number of recursive calls snowballs.

There are ways of working around this problem, but I hope this serves to illustrate the risks of working with recursion without a full understanding of what is happening behind the scenes.

#### Limitations on recursion

In Python, there are also some internal limitations on just how may times you can keep calling a function. Eventually you will get a RecursionError that looks a little like this:

In [20]: def dontdothis():
...:     dontdothis()
...:

In [21]: dontdothis()
---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-57-4e25188c60e4> in <module>
----> 1 dontdothis()

<ipython-input-56-753bb23d7435> in dontdothis()
1 def dontdothis():
----> 2     dontdothis()
3

... last 1 frames repeated, from the frame below ...

<ipython-input-56-753bb23d7435> in dontdothis()
1 def dontdothis():
----> 2     dontdothis()
3

RecursionError: maximum recursion depth exceeded


And if you're curious about just how many times I was allowed dig deeper into this recursive function stack, let's change the dontdothis function to show us a counter when it bombs out.

In [22]: def dontdothis(n=0):
...:     n += 1
...:     try:
...:         dontdothis(n)
...:     except RecursionError:
...:         print(f"Recursion error at count: {n}")
...:

In [23]: dontdothis()
Recursion error at count: 2985


## Summary

The main takeaway from this should be that recursion is a powerful tool, but use it with caution.

"Recursion is a powerful tool, but use it with caution."