bunnies love one another
a lot
if you put a pair of rabbits in a vast
field covered in fresh grass they will
reproduce like mad
the number of fluffy pears grows
according to the fibonacci sequence to
write a function giving the terms of the
fibonacci sequence you will need
recursion
to make this function efficient we will
use memorization
let's get ready
to count bunnies
the first few terms of the fibonacci
sequence are
1 1
2
3
5 8 13 21
here is how the sequence is constructed
the first two terms are ones
thereafter each term is the sum of the
previous two terms
one plus one is two the third term
one plus two equals three the fourth
term
two plus three is five
three plus five is eight
five plus eight is thirteen
and eight plus thirteen is twenty one
this process continues forever
our goal is to write a function
returning the nth term of the fibonacci
sequence
our function should be fast clearly
written and rock solid
you may think this will be simple but by
the time we are done with our function
it will be more complex than you may
expect
by the way
some people argue that the sequence
should start with 0 and one
if you encounter this situation
don't panic
other than the zero the two sequences
are identical
people love to debate the smallest of
details
let's now write the function
we begin by giving our function a name
we will follow the python style guide
and use all lowercase letters for the
name of our function
there is a single input n
this function will return the nth term
to begin we handle the starting cases
if n equals one we return the first term
one
if n equals two
we return the second term one
if n is larger than two we return the
sum of the previous two terms
because this function is calling itself
we call it a recursive function
let's test this function to see if it
works
we will print the first 10 terms
notice that our range is from 1 to 11
not one to ten
that is because the range function does
not include the final number
frustrating
i know
now run
our function worked
does this mean we are done
before we move on let's test our
function for a few more values
what if we display the first 100 terms
of the fibonacci sequence
run
well
this is disappointing our function is
slowing down
it's virtually useless beyond a few
dozen terms
why is this and how can we fix this
to see why this function is so slow look
what happens when it computes the fifth
term of the sequence
because this is a recursive function
fibonacci 5 returns fibonacci 4 plus
fibonacci 3. but fibonacci 4 returns
fibonacci 3 plus fibonacci 2 and
fibonacci 3 equals fibonacci 2 plus
fibonacci 1.
but now the function must make another
recursive call because fibonacci 3
equals fibonacci 2 plus fibonacci 1.
our poor computer is repeating itself
needlessly
since fibonacci 1 and fibonacci 2 are
both 1 we finally get the answer
5.
our simple recursive function is
careless
we are making it repeat itself over and
over and over
and over
there is a simple cure to this madness
memorization
the idea behind memoization is simple
store the values for recent function
calls so future calls do not have to
repeat the work
there are several ways to do this in
python
we will first implement memorization
explicitly so you can see how it works
then we will use a built-in python tool
that makes memoization trivial
to begin create a dictionary called
fibonacci cache which will store recent
function calls
next let's rewrite the fibonacci
function to make use of cached values
the first thing we will do is check to
see if the value for the nth term is in
our cache
if it is then simply return it
otherwise we must compute the nth term
but we will handle this differently than
before
we do not want to simply return the
value
instead we will first compute the value
cache it then return it
we compute the nth term the same as
before the first and second terms are
both one
otherwise we make a recursive call to
compute the nth term
finally store the return value in our
fibonacci cache dictionary then return
it
let's see if this function performs
better than our first attempt
much better
let's really put this function to the
test and display the first 1000 terms
impressive
now that you have seen an explicit
implementation of memorization
i would like to show you a simpler
approach
for this let's return to our first
version of the function
this function is appealing it is clean
and simple
from the funk tools module import a
decorator called lru cache
this stands for least recently used
cache and it provides a one-line way to
add memorization to your functions
to use this write at lru cache before
our function
in parentheses enter the number of
values to cache
by default python will cache the 128
most recently used values so if you do
not specify a max size you will still
see benefits
our original function will now operate
very quickly
as proof let's print the first 500
values
much better
a simple function with fast performance
but our work is not done
what if we call the function and pass in
the value 2.1
or negative one
or the string
one in all cases the function did not
know what to do
that is because we did not first check
that the argument was a positive integer
let's fix this
first check that the input is an integer
if it is of the wrong type then raise a
type error telling the user what
argument is expected
next
verify that the argument is a positive
integer
if not
raise a value error with the same
message
now if we call our fibonacci sequence
with a float
non-positive integer
or any other forbidden value the user
will receive a helpful error message
by the way there are many ways this
method can be shortened but we have
opted for clarity over compactness
short and clever code can be fun to
write but it often torments others
let's take a final look at the first 50
fibonacci numbers
as you can see the numbers grow quickly
in size but how quickly
to see we will compute the ratio between
consecutive terms
interesting
the ratio between consecutive terms in
the fibonacci sequence
appears to converge to a number in fact
the ratios converge to the golden ratio
you can learn more about this in our
video on the fibonacci sequence and the
golden ratio
like rabbits recursive functions can
quickly take over
caution must be exercised
otherwise like fibonacci you will end up
with a fuzzy wuzzy mess on your hands
you