⇐ Use this menu to view and help create subtitles for this video in many different languages.
You'll probably want to hide YouTube's captions if using these subtitles.

# Stepping Through Recursive Fibonacci Function: Understanding why and how the recursive Fibonacci function works

相關課程

選項
分享

0 / 750

- 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

載入中...