Recursive Fibonacci Example Using recursion to write a fibonacci function
Recursive Fibonacci Example
⇐ 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.
- if you havent tried already to write your own recursive fibonacci sequence function
- i really encourage you to do so, or at least to try to do so
- give it a serious debt before you watch this video
- but if you have done that, or your feeling lazy
- i guess you can watch this video
- and so we're going to try to write a fibonnaci function
- according to thespecs that i laid out when i first set up the challenge to write a fibonacci function
- so ill call this fibonacci again fi-bo-nacci
- fibonacci and it will take it
- it has a parameter here, n, and it will pass an argument
- to it to say which term do we want of the fibonacci sequece
- but here we're going to do it recursively and what we're going to see
- is that it's actually a very intuitive to write a fibonacci function
- recursively, al-its like-almost-like
- magic, and later we will see that it is not necessarily the
- most efficient way to write the fibonacci function
- so what im gonna do is, whenever you, 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
- theres actually two base cases
- theres the zeroeth term and the first term
- and those are really given by definition
- so lets just say,
- if, if we want the zeroeth term
- so if n is equal to zero,
- if n is equal to zero,
- well, that means you want the zeroeth term
- and the zeroeth term is actually zero!
- and you could say, else if,else if
- n is equal to one, n is equal to one,
- then you, then you can return
- then you can return
- you can return, one!
- that is the zero term is zero, the first term in the fibonacci sequence
- is one.
- and now here is a little bit of where the magic happens.
- otherwise, otherwise, return -and now this is really cool here-
- return to the fibonacci, fib-o-nacci
- of n minus one,so whenever the previous term in
- the fibonacci sequence is, plus fibonacci, plus fibonacci,
- of n minus 2.
- and i think this should work. and that's why it seems magical.
- cuz all we're saying is hey look, if you the zero term its zero
- if you want the first term, its one
- -lets give some spaces here-
- if you want the first term, it is one!
- if you want any other term, -if you want any other term-
- so else, if you want- this is else if-
- e-bu- else neither of these is true so neither
- zero nor one if its some other number, its going to be
- - and we're going to assume that your inputting some, some
- non-negative integer over here-
- right over here-
- this would break down if you did something non-negative
- integer over non-negative uh, negative, term
- but if, assuming you have, uh, a non-negative integer,
- then you say look!
- if its not the zeroeth term or the first term
- then just take
- the fibonnaci of the, whatever term one term less than it is
- plus two terms less than that, and you could try it
- out, for example:
- lets say you took the fibonacci of 2!
- or,then, n is not zero
- then you wont do this
- n is not one so you wont do this
- but you'll say return fibonacci of 2 minus 1
- so thats fibonacci of 1
- plus fibonacci of 2 minus 2 plus fibonacci of 0.
- but we know fibonacci of one, evaluates to one
- fibonacci of zero evaluates to zero
- so it'll be one plus zero,
- just one!
- And you can keep going!
- try fibonacci of 3!
- it'll work!
- because we know fibonacci of 0,1,or 2 works
- cuz fibonacci of 3 will boil down to fibonacci of 2 plus fibonacci of 1.
- we know that fibonacci of 2 is 1, fibonacci of 1 is 1
- 1+1 is 2
- so it'll just keep working.
- now we could try it out
- let's just save this
- -actually didn't save the file name called recursive fibonacci-
- -repeat twice-
- and now let me actually run the program
- and all this does is define the function
- in-in my environment that i actually have to call the function.
- so let me just run it
- and let me ask for fibonacci offfff 4.
- it gave me the right answer.
- fi-bo-nacci of 10!
- 55, right answer.
- fibonacci, -i could try simple things, fibonacci of zero
- of the zero term is zero
- so it all works out
- so thats why recursion is kinda magical.
- and if you wanted to simplify this any more, you might
- recognize, hey! the zeroeth term of the fibonacci sequence
- is zero, the first term of the fibonacci sequence is one,
- so really, its-it-if your asking for the zeroeth or the first term
- its really the same thing of as that number.
- so you could actually maybe simplify this a little bit
- if you assume that someone was going to input a non-negative integer
- over here, you could say something like-
- if n, if n is equal to zero or n is equal, or n is equal to 1,
- - or n is equal to 1,-
- return, return n!
- Lets see if this works.
- lets see if it simplified our code up a little bit
- so lets try this- save this,
- and now lets run it,
- lets run it,
- alright, and now lets try fi-bo-nacci, fibonacci of 10!
- it still worked!
- cuz really, the zeroeth term is zero, and the nth term is
- or uh the first term is one,-so that works there-
- or you can even simplify more
- if n is less than 2! that should also work
- becuz then if its zero or one your gonna return n, and otherwise
- your gonnna return to this business
- so lets try that out.
- so we ran it, and lets try fibonacci fibonacci of, fibonacci of 10
- now. it seems that the computer is able to do this
- really quickly and all of that and all the rest of it
- but if you really wanna see
- all the work that's being done, all the calls to fibonacci
- what you can do is
- lets put a print in here
- so that every time fibonacci gets called print, it prints
- fibonacci it prints the text fibonacci COLON, and then,
- pl- i'm going to add to that string, to that string of text
- what, what the argument is.
- so the argument of this is going to be n,
- and i wanna make sure that its viewed as a string.
- So i'll put, i'll put it, im casting it to a string
- that's essentially just taking
- an integer and making sure its a string, and when i add it
- to this string, it'll make it one big string
- but lets see what this does
- i'm gonna try it out with lower values first
- so let me,...., the function is defined
- Fibonacci,-I can just-
- let me do Fibonacci off 3
- so notice,
- when it 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, it had to call Fibonacci of zero
- 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 me the answer.
- If you did like Fibonacci of 10, its gonna go really
- crazy, so I'm gonna do that
- let me, let me just do Fibonacci of like 6,
- and your gonna see how many calls to Fibonacci it had to do
- so it had to do all of these calls, all of these calls, to fibonacci
- so it was actually very computationally intensive
- thing to do.
- but it, you know, the computer's are super fast, so
- you dont even notice it. But in the future we're going to talk about
- a little bit more how do we think about how computationally-intensive
- different ways of implementing a function,
Be specific, and indicate a time in the video:
At 5:31, how is the moon large enough to block the sun? Isn't the sun way larger?
Have something that's not a question about this content?
This discussion area is not meant for answering homework questions.
Share a tip
When naming a variable, it is okay to use most letters, but some are reserved, like 'e', which represents the value 2.7831...
Have something that's not a tip or feedback about this content?
This discussion area is not meant for answering homework questions.
Discuss the site
For general discussions about Khan Academy, visit our Reddit discussion page.
Flag inappropriate posts
Here are posts to avoid making. If you do encounter them, flag them for attention from our Guardians.
- disrespectful or offensive
- an advertisement
- low quality
- not about the video topic
- soliciting votes or seeking badges
- a homework question
- a duplicate answer
- repeatedly making the same post
- a tip or feedback in Questions
- a question in Tips & Feedback
- an answer that should be its own question
about the site