1
00:00:00,690 --> 00:00:02,250
So here's one way to solve this, we're
2
00:00:02,250 --> 00:00:04,770
going to define a procedure Fibonacci and we'll call the
3
00:00:04,770 --> 00:00:07,160
input n. And now we need to write
4
00:00:07,160 --> 00:00:09,930
the code, and if we remember our definitions; so
5
00:00:09,930 --> 00:00:14,550
we said Fibonacci of 0 is defined as 0,
6
00:00:14,550 --> 00:00:20,640
Fibonacci of 1 is defined as 1. And Fibonacci of any higher number
7
00:00:20,640 --> 00:00:25,780
is defined as Fibonacci of n minus 1 plus Fibonacci of n
8
00:00:25,780 --> 00:00:28,570
minus 2. So if you remember the definition, we
9
00:00:28,570 --> 00:00:31,520
have two base cases we need to consider. If the
10
00:00:31,520 --> 00:00:33,980
input value is 0, or the input value is 1,
11
00:00:33,980 --> 00:00:36,910
we need to do something special. So we could write
12
00:00:36,910 --> 00:00:40,560
those as separate if statements. So if n is
13
00:00:40,560 --> 00:00:43,965
equal to 0, what we want to do is return
14
00:00:43,965 --> 00:00:50,980
0. If n is equal to 1, what we want to do is return 1. Otherwise what we want to
15
00:00:50,980 --> 00:00:56,182
do is the recursive part of the definition. So we want
16
00:00:56,182 --> 00:01:00,835
to return the result of Fibonacci n minus 1, and we want
17
00:01:00,835 --> 00:01:04,879
to add that to Fibonacci n minus 2. So we could
18
00:01:04,879 --> 00:01:08,280
simplify this a little bit. Let's try this in the Python interpreter.