If you haven't tried already to write
your own recursive Fibonacci function,
I really encourage you to do so, or at least to try to do so.
Give it a serious attempt before you watch this video.
But if you have done that, or if you're feeling lazy,
I guess you can watch this video.
And so we're going to try to write a recursive Fibonacci
function according to the specs that I laid out when I first
set up the challenge to write a Fibonacci function.
So I'll call this Fibonacci again, and it'll take it.
It has a parameter here, n.
So someone will have to pass an argument to it
to say which term do we want of the Fibonacci sequence,
but here we're going to do it recursively.
And what we're going to see is that it's actually
very intuitive to write a Fibonacci function recursively.
It's almost like magic.
And later we'll see, though, it's not necessarily
the most efficient way to write a Fibonacci function.
So what I'm going to do is whenever you write
any recursive program, you really
need to think about the base cases really well.
And the base cases of the Fibonacci sequence, there's
actually two base cases.
There's the 0-th term and the first term,
and those are really given by definition.
So let's just say if we want the 0-th term, if n is equal to 0,
well, that means you want the 0-th term,
and the 0-th term is actually 0.
And you could say else if n is equal to 1,
then you can return 1, because the 0-th term is 0.
The first term in the Fibonacci sequence is 1.
And now here is where a little bit of the magic happens.
Otherwise return-- and this is really cool
here-- the Fibonacci of n minus 1.
So whatever the previous term in the Fibonacci sequence
is plus Fibonacci of n minus 2.
And I think this should work.
And that's why it seems magical, because all we're saying
is, hey, look, if you want the 0-th term, it's 0.
If you want the first term, it's 1--
Let me put two spaces here-- if you want the first term,
it is 1.
If you want any other term, so else-- and this is else
if-- but else if neither of these are true,
if it's neither 0 nor 1, if it's some other number,
it's going to be-- and we're going
to assume that you're inputting some non-negative integer
over here.
This would break down if you did some non-negative integer
over the non-negative term.
But assuming you have a non-negative integer,
then you say, look, if it's not the 0-th or the first term,
then just take the Fibonacci of whatever one term
less than it is, plus two terms less than that.
And you could try it out.
For example, let's say you took Fibonacci of 2.
Then n is not 0, so you won't do this, and n is not 1,
so you wouldn't do this.
So you'll say return Fibonacci of 2 minus 1.
So that's Fibonacci of 1, plus Fibonacci of 2 minus 2,
plus Fibonacci of 0.
Well, we know Fibonacci of 1 evaluates to 1,
and Fibonacci of 0 evaluates to 0, so it'll be 1 plus 0,
or just 1.
And you could keep going.
Try Fibonacci of 3.
It'll work because we know Fibonacci of 0, 1, or 2 works.
Because Fibonacci of 3 will boil down
to Fibonacci of 2 plus Fibonacci of 1,
we know that Fibonacci of 2 is 1, and Fibonacci of 1 is 1.
So it'll be 1 plus 1 is 2, so it'll just keep working.
And we could try it out.
Let's just save this.
Actually I didn't save the file name, let me just call it
Recursive Fibonacci.
It's a dot py file.
And now let me actually run the program.
And all this does is define the function in my environment.
And then I'd actually have to call the function.
So let me just run it.
And let me ask for Fibonacci of 4.
It gave me the right answer.
Fibonacci of 10, 55.
Right answer.
I could try simple things.
Fibonacci of 0, the 0-th term is 0.
So it all works out.
So that's why recursion is kind of magical.
And if you wanted to simplify this anymore,
you might recognize, hey, the 0-th term of the Fibonacci
sequence is 0; the first term of the Fibonacci sequence is 1;
so really if you're looking for the 0-th term
or the first term, it's really the same thing as that number.
So you could actually, maybe, simplify this a little bit.
If you assume that someone is going
to input a non-negative integer over here,
you could say something like if n is equal to 0,
or n is equal to 1, return n.
Let's see if this works.
So this simplified our code up a little bit.
So let's try to save this.
And now let's run it.
And now let's try,
Fibonacci of 10.
It still worked, because really the 0-th term is 0,
and the first term is 1.
So it works there, or you could even simplify it more.
If n is less than 2, that should also work, because then if it's
0 or 1 you're going to return n, and otherwise you're
going to do all of this business.
So let's try that out.
So we ran it.
And let's try Fibonacci of 10.
Now, it seems like the computer is
able to do this really quickly, and all of that,
and all the rest of it.
But if you really want to see all of the work that's
being done, all the calls to Fibonacci,
what you can do is-- let's put a print in here.
So that every time Fibonacci gets called,
it prints the text Fibonacci colon.
And then I'm going to add to that string of text
what the argument is.
So the argument in this is going to be n,
and I want to make sure that it is viewed as a string.
I'm casting it to a string.
That's essentially just taking an integer
and making sure it's a string, and then
when I add to this string, it'll make it one big string.
But let's see what this does.
I'm going to try it out with lower values first.
So the function is defined.
So let me write Fibonacci of 3.
So notice when I called, it called Fibonacci of 3.
Then to do Fibonacci of 3, it had to call Fibonacci of 2
and Fibonacci of 1.
And then to do Fibonacci of 2, it had to call Fibonacci of 0
and Fibonacci of 1.
So it had to do all of these calls to Fibonacci
just to calculate the Fibonacci of 3,
and then eventually it gave you the answer.
If you did Fibonacci of 10, it's going to go really crazy.
So I'm not even going to do that.
Let me just do Fibonacci of 6, and you're
going to see how many calls to Fibonacci it had to do.
So it had to do all of these calls to Fibonacci.
So it was actually a very computationally intensive thing
to do.
But the computers are super fast,
so you don't even notice it.
But in the future we'll talk a little bit more
of how do we think about how computationally
intensive different ways of implementing a function can be.