[Script Info]
Title:
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.69,0:00:02.25,Default,,0000,0000,0000,,So here's one way to solve this, we're
Dialogue: 0,0:00:02.25,0:00:04.77,Default,,0000,0000,0000,,going to define a procedure Fibonacci and we'll call the
Dialogue: 0,0:00:04.77,0:00:07.16,Default,,0000,0000,0000,,input n. And now we need to write
Dialogue: 0,0:00:07.16,0:00:09.93,Default,,0000,0000,0000,,the code, and if we remember our definitions; so
Dialogue: 0,0:00:09.93,0:00:14.55,Default,,0000,0000,0000,,we said Fibonacci of 0 is defined as 0,
Dialogue: 0,0:00:14.55,0:00:20.64,Default,,0000,0000,0000,,Fibonacci of 1 is defined as 1. And Fibonacci of any higher number
Dialogue: 0,0:00:20.64,0:00:25.78,Default,,0000,0000,0000,,is defined as Fibonacci of n minus 1 plus Fibonacci of n
Dialogue: 0,0:00:25.78,0:00:28.57,Default,,0000,0000,0000,,minus 2. So if you remember the definition, we
Dialogue: 0,0:00:28.57,0:00:31.52,Default,,0000,0000,0000,,have two base cases we need to consider. If the
Dialogue: 0,0:00:31.52,0:00:33.98,Default,,0000,0000,0000,,input value is 0, or the input value is 1,
Dialogue: 0,0:00:33.98,0:00:36.91,Default,,0000,0000,0000,,we need to do something special. So we could write
Dialogue: 0,0:00:36.91,0:00:40.56,Default,,0000,0000,0000,,those as separate if statements. So if n is
Dialogue: 0,0:00:40.56,0:00:43.96,Default,,0000,0000,0000,,equal to 0, what we want to do is return
Dialogue: 0,0:00:43.96,0:00:50.98,Default,,0000,0000,0000,,0. If n is equal to 1, what we want to do is return 1. Otherwise what we want to
Dialogue: 0,0:00:50.98,0:00:56.18,Default,,0000,0000,0000,,do is the recursive part of the definition. So we want
Dialogue: 0,0:00:56.18,0:01:00.84,Default,,0000,0000,0000,,to return the result of Fibonacci n minus 1, and we want
Dialogue: 0,0:01:00.84,0:01:04.88,Default,,0000,0000,0000,,to add that to Fibonacci n minus 2. So we could
Dialogue: 0,0:01:04.88,0:01:08.28,Default,,0000,0000,0000,,simplify this a little bit. Let's try this in the Python interpreter.