Stepping Through Recursive Fibonacci Function
Stepping Through Recursive Fibonacci Function
Understanding why and how the recursive Fibonacci function works
Content
0.933 -> What I want to do in this video
2.948 -> is make sure we really understand what is going on
5.133 -> when we call our recursive fibonacci functions
8.067 -> So I'm going to assume that someone calls it with
10.85 -> an argument of and they give pass 5 as an argument
16.2 -> I don't want to pick too large of a number
18.733 -> cuz otherwise I'll be explaining it forever
21.267 -> So let's try fibonacci(5)
23.2 -> So in this situation, within the context of this function
27.067 -> the parameter n right here is going to be equal to 5
32.467 -> so in that first pass, the parameter n is going to be equal to 5
37.4 -> The way we wrote it
39.313 -> we said that if n < 2 return n
41.129 -> 5 is definitely not less than 2
42.867 -> so we're going to go to the else part of the if clause
46.133 -> or the else clause and say return
49.138 -> fibonacci of (n-1) plus fibonnaci of (n-2))
53.1 -> so when I call this it's eventually be reduced to
55.8 -> if you want to think about it that way, or simplified
58.656 -> it would return, what is going to be the same thing as fibonacci of
67.005 -> remember n was 5
69.6 -> so n-1 is 4
74.611 -> plus fibonacci of n-2, which when we ran the function n was 5
80.395 -> so 5-2 is 3
82.246 -> well these are just more function calls
84.595 -> so now we are going to go again
86.729 -> n is not 5, but 4 and 3
88.718 -> so let's try this out
90.6 -> so over here n is equal to 4
94.467 -> n is equal to 4
98.2 -> so once again 4 is not less than 2,
100.6 -> so we don't do this part
102.867 -> we go to the else
104.552 -> we then return fibbonacci(4-1) which is 3
107.467 -> so this is going to simplify to,
109.933 -> or breakdown I should say
113.61 -> to fibonnacci of 4-1 which is 3
116.641 -> plus fibbonacci of 4-2
124.12 -> which is fibonaacci of 2
124.62 -> so this right over here will essenitally return this
129.467 -> and this over here on the right fibonacci of 3
134.467 -> let me draw, because these are going to get jumbled up soon
137.641 -> so this returns this stuff in magenta
142.169 -> and this stuff I've underlined in green will return
146.4 -> n is now 3; 3 is not less than 2
149.359 -> so you go here
152.346 -> and it will return fibonacci of 3-1 which is fibbonacci (2)
162.133 -> and plus fibonacci of 3-2, which is fibonacci (1)
171.467 -> and then we're going to go over here
173.523 -> and we're going to have to calculate each of these things
176.021 -> and these are just more calls to fibonacci
179.133 -> and fibonacci(3), so you can see how this is getting pretty involved right now
182.667 -> I'm going to start writing fib short for fibonacci
184.933 -> so that I don't run out of real estate
187.8 -> fibonacci (3) when you call it
191.231 -> n 3 is not less than 2
193.72 -> that reduces to fibonacci (3-1)
198.933 -> I'll just write fib. short for fibonacci
201.267 -> fibonacci of 2 plus fibbonacci of (3-2)
206.262 -> plus fibonacci of 1
209.298 -> so it reduces to that or breaks down to that
212.662 -> and over here fibonacci of 2
215.933 -> 2 is not less than 2,
218.452 -> so we are going to have to return fibonacci of 2 -1
222.434 -> fibonacci of 1 plus fibonacci of 2-2
223.6 -> so plus fibonacci of 0
229.933 -> so it breaks down to those two calls to fibonacci
233.8 -> and over here fibonacci(2) same thing.
236.025 -> we made a call to fibonacci(2)
238.144 -> that's going to break down just like that fibonacci(2) did
241.08 -> it will break down to a call
243.323 -> to of fibbonacci of 1 and fibonacci(0)
248.182 -> and then we have fibonacci of 1
249.978 -> so this is interesting.
251.374 -> Because when n is equal to 1
253.138 -> this clause up here suddenly becomes relevant
256.336 -> Because n is less than 2 and it says return n
260.025 -> so this, this right here is going to simplify
262.8 -> this term right over here is going to simplify to 1
266.105 -> it is going to evaluate to 1
268.569 -> And then we look at all of these over here
270.713 -> fibonacci (2); we know that fibonacci(2) results in fib(1) + fib(0)
276.841 -> so let me write that over here
279.308 -> so over here is fibbonacci(1) plus fibbonacci(0)
284.052 -> fibb is short for fibonacci
286.302 -> and then we know fibbonacci of 1
289.6 -> 1 is less than 2, so return n
292.133 -> so this is going to return 1
296.533 -> fibonacci of 1 just returns 1
298.933 -> fibonacci of 0
300.533 -> and 0 is less than 2, returns 0
302.133 -> so fibonacci(0) just returns 0
303.633 -> fibonacci of 0 returns 0
305.133 -> fibonacci of 1 returns 1
307.8 -> fibonacci of 0 returns 0
309.821 -> and then fibonacci of 1 returns 1
312.733 -> fibonacci of 0 returns 0
314.395 -> So the whole time the interpreter is processing this recursive function call
320.8 -> it kinda has to remember all of the previous, how it got there
323.933 -> because once it eventually gets down to the base cases,
327.492 -> once it gets down to the n = 1 or 0
330.733 -> it actually gets a numeric response
331.833 -> it then has to build up to it's previous reponse
332.933 -> so fibbonacci(2) right over here
335.148 -> is 1 + 0
339.148 -> fibbonacci of(2) is going to simplify to 1
342.687 -> This fibonacci(3) is fibonacci(2) + fibbonacci(1)
347 -> those get simplified to 1
348.205 -> so this is going to be 1 + 1
352.095 -> so this is going to be 2
353.363 -> We go over here fibbonacci of(2)
354.415 -> fibbonacci(1) + fibbonacci(0) = 1
358.744 -> fibbonacci(2)
360.118 -> 1+0 is 1
363.175 -> We go over to fibonacci of 1, this is 1
365.252 -> And now we go up to this level
366.138 -> we're kind of retructuring back until we get back to the original function call
370 -> And I'm not going to go ito the details
372.133 -> about how the interpreter is actually doing that
373.636 -> because this is acutally a fascinating discussion
375.8 -> but I'll just think about how we think about what is happening
377.933 -> during in thisrecursive function call, and why, why is is working
380.267 -> why is it gving us the right answer
383.733 -> And then we go over here fibonacci(4)
385.4 -> well fibonacci(4), the fourth fibonacci term
389.144 -> is the sum of the third and the second fibonacci term
391.759 -> which we have already figured out
393.733 -> they are two and one, you just take their sum and get 3
397.738 -> the third fibonacci term, by the definition of the fibonacci sequence
401.2 -> is the sum of the first and the second term
404.067 -> those are each one
406.636 -> the sum of one plus one is two
409.175 -> the fifth term, the fifth fibonacci number
411.913 -> the fifth fibonacci term
414.013 -> is the sum of the fourth and the third terms
416.867 -> those are three and two
418.887 -> so three plus two is five
421.338 -> so this things right over here is going to evaluate to 5
425.067 -> So hopefully that clarifies a little bit
427.133 -> about how this recusive program is actually working
429.6 -> what's neat about it is
431.308 -> that it wouldn't work if you didn't go down and define
433.467 -> the base cases of fibonacci(1) and fibonacci(0)
435.8 -> It would just keep calling itself forever, and never get anywhere
437.733 -> and what they key with recursion is that it can call itself
441.4 -> as long as every time it calls itself
445.133 -> it's making its way down to the base cases
447.6 -> so at some point
449.4 -> if it keeps calling itself, it keeps calling itself
451.267 -> eventually it's able to build back those calls
455.846 -> to get back to the base cases
457.452 -> and then recontruct what the original value was from that
460.467 -> and that's why its working
462.467 -> each call to fibonacci is a simpler version
465.2 -> I have a lower n
466.533 -> and eventually my n are going to get to the base cases
468.333 -> which will actually give me actual values
475.733 -> which I can then recontruct for our original calls
477.6 -> hopefully that helps a little bit
479 -> recursion can be confusing
479.5 -> but at the same time
480.082 -> it can also be elegant and beautiful in it's own way
Source: https://www.youtube.com/watch?v=zg-ddPbzcKM