What I want to do in this video
is make sure we really understand what is going on
when we call our recursive fibonacci functions
So I'm going to assume that someone calls it with
an argument of and they give pass 5 as an argument
I don't want to pick too large of a number
cuz otherwise I'll be explaining it forever
So let's try fibonacci(5)
So in this situation, within the context of this function
the parameter n right here is going to be equal to 5
so in that first pass, the parameter n is going to be equal to 5
The way we wrote it
we said that if n < 2 return n
5 is definitely not less than 2
so we're going to go to the else part of the if clause
or the else clause and say return
fibonacci of (n-1) plus fibonnaci of (n-2))
so when I call this it's eventually be reduced to
if you want to think about it that way, or simplified
it would return, what is going to be the same thing as fibonacci of
remember n was 5
so n-1 is 4
plus fibonacci of n-2, which when we ran the function n was 5
so 5-2 is 3
well these are just more function calls
so now we are going to go again
n is not 5, but 4 and 3
so let's try this out
so over here n is equal to 4
n is equal to 4
so once again 4 is not less than 2,
so we don't do this part
we go to the else
we then return fibbonacci(4-1) which is 3
so this is going to simplify to,
or breakdown I should say
to fibonnacci of 4-1 which is 3
plus fibbonacci of 4-2
which is fibonaacci of 2
so this right over here will essenitally return this
and this over here on the right fibonacci of 3
let me draw, because these are going to get jumbled up soon
so this returns this stuff in magenta
and this stuff I've underlined in green will return
n is now 3; 3 is not less than 2
so you go here
and it will return fibonacci of 3-1 which is fibbonacci (2)
and plus fibonacci of 3-2, which is fibonacci (1)
and then we're going to go over here
and we're going to have to calculate each of these things
and these are just more calls to fibonacci
and fibonacci(3), so you can see how this is getting pretty involved right now
I'm going to start writing fib short for fibonacci
so that I don't run out of real estate
fibonacci (3) when you call it
n 3 is not less than 2
that reduces to fibonacci (3-1)
I'll just write fib. short for fibonacci
fibonacci of 2 plus fibbonacci of (3-2)
plus fibonacci of 1
so it reduces to that or breaks down to that
and over here fibonacci of 2
2 is not less than 2,
so we are going to have to return fibonacci of 2 -1
fibonacci of 1 plus fibonacci of 2-2
so plus fibonacci of 0
so it breaks down to those two calls to fibonacci
and over here fibonacci(2) same thing.
we made a call to fibonacci(2)
that's going to break down just like that fibonacci(2) did
it will break down to a call
to of fibbonacci of 1 and fibonacci(0)
and then we have fibonacci of 1
so this is interesting.
Because when n is equal to 1
this clause up here suddenly becomes relevant
Because n is less than 2 and it says return n
so this, this right here is going to simplify
this term right over here is going to simplify to 1
it is going to evaluate to 1
And then we look at all of these over here
fibonacci (2); we know that fibonacci(2) results in fib(1) + fib(0)
so let me write that over here
so over here is fibbonacci(1) plus fibbonacci(0)
fibb is short for fibonacci
and then we know fibbonacci of 1
1 is less than 2, so return n
so this is going to return 1
fibonacci of 1 just returns 1
fibonacci of 0
and 0 is less than 2, returns 0
so fibonacci(0) just returns 0
fibonacci of 0 returns 0
fibonacci of 1 returns 1
fibonacci of 0 returns 0
and then fibonacci of 1 returns 1
fibonacci of 0 returns 0
So the whole time the interpreter is processing this recursive function call
it kinda has to remember all of the previous, how it got there
because once it eventually gets down to the base cases,
once it gets down to the n = 1 or 0
it actually gets a numeric response
it then has to build up to it's previous reponse
so fibbonacci(2) right over here
is 1 + 0
fibbonacci of(2) is going to simplify to 1
This fibonacci(3) is fibonacci(2) + fibbonacci(1)
those get simplified to 1
so this is going to be 1 + 1
so this is going to be 2
We go over here fibbonacci of(2)
fibbonacci(1) + fibbonacci(0) = 1
fibbonacci(2)
1+0 is 1
We go over to fibonacci of 1, this is 1
And now we go up to this level
we're kind of retructuring back until we get back to the original function call
And I'm not going to go ito the details
about how the interpreter is actually doing that
because this is acutally a fascinating discussion
but I'll just think about how we think about what is happening
during in thisrecursive function call, and why, why is is working
why is it gving us the right answer
And then we go over here fibonacci(4)
well fibonacci(4), the fourth fibonacci term
is the sum of the third and the second fibonacci term
which we have already figured out
they are two and one, you just take their sum and get 3
the third fibonacci term, by the definition of the fibonacci sequence
is the sum of the first and the second term
those are each one
the sum of one plus one is two
the fifth term, the fifth fibonacci number
the fifth fibonacci term
is the sum of the fourth and the third terms
those are three and two
so three plus two is five
so this things right over here is going to evaluate to 5
So hopefully that clarifies a little bit
about how this recusive program is actually working
what's neat about it is
that it wouldn't work if you didn't go down and define
the base cases of fibonacci(1) and fibonacci(0)
It would just keep calling itself forever, and never get anywhere
and what they key with recursion is that it can call itself
as long as every time it calls itself
it's making its way down to the base cases
so at some point
if it keeps calling itself, it keeps calling itself
eventually it's able to build back those calls
to get back to the base cases
and then recontruct what the original value was from that
and that's why its working
each call to fibonacci is a simpler version
I have a lower n
and eventually my n are going to get to the base cases
which will actually give me actual values
which I can then recontruct for our original calls
hopefully that helps a little bit
recursion can be confusing
but at the same time
it can also be elegant and beautiful in it's own way