So here's one way to solve this, we're
going to define a procedure Fibonacci and we'll call the
input n. And now we need to write
the code, and if we remember our definitions; so
we said Fibonacci of 0 is defined as 0,
Fibonacci of 1 is defined as 1. And Fibonacci of any higher number
is defined as Fibonacci of n minus 1 plus Fibonacci of n
minus 2. So if you remember the definition, we
have two base cases we need to consider. If the
input value is 0, or the input value is 1,
we need to do something special. So we could write
those as separate if statements. So if n is
equal to 0, what we want to do is return
0. If n is equal to 1, what we want to do is return 1. Otherwise what we want to
do is the recursive part of the definition. So we want
to return the result of Fibonacci n minus 1, and we want
to add that to Fibonacci n minus 2. So we could
simplify this a little bit. Let's try this in the Python interpreter.