Recursion is a development technique that is popular among developers, so it can be a common question during interviews. Take a look at what it is and, more importantly, when it is useful.
- [Instructor] Recursion is a programming technique that is popular among developers. So it can be a common question during interviews. Let's take a look at what it is and more importantly when it is useful. Now recursion sounds a lot fancier and more complicated than it really is. To put it simply, recursion happens anytime a function calls itself. Now it's a dangerous technique for obvious reasons. If you take a look at this example, you'll see that this function called myself calls itself indefinitely.
And this would happen until the computer runs out of memory. So at the very least, every recursive function needs something called a base case. That's a statement that exists a function when a condition is met. You can see that in this simple example we're using this function called count up to count up from one to the number five. We're doing the recursion right here when this function calls itself with the next number, and it keeps on going until it reaches this condition.
Now at the very least it's going to lock up your browser while this is going on, which is never a good experience. Now looking at this example, you might be asking yourself why wouldn't you just use a loop to count up to five here? Well, let's take a look at another more complicated example. Now this is a more typical interview question for recursion. I'm trying to calculate something called Fibonacci numbers. That's a series of numbers where each new number is the result of an addition of the previous two numbers.
It's a pattern that appears commonly in the natural world. Now we're using recursion to calculate the sum of a series of numbers. We're calling this function fibby right here because it's a little bit easier than writing out Fibonacci. At the end of this function it's going to return an array of all of the numbers in the sequence when we call the function with this fibby 8 right here. In this cause our base case is right here, and it's going to return the first two numbers in the array, which since we're adding up two numbers, we have to have two numbers to begin with.
In this case those two numbers are zero and one. What we're going to do after that is the actual recursion itself. So next time we're going to call this function with the variable that is one less than the original number. So in that case it'll get fibby and then the number 7 for the next call to this new function. Now after that we do everything we need to do in the function, and what we're going to return is an array that is the sum of the previous two numbers.
So in essence, the first time that this gets added up it's going to add up zero and one, and the third element would be another one. Which is correct for Fibonacci numbers. Each time it sums up the numbers it's going to push them into a new array. So let's take a look at what's happening here with a few more console statements. So you can see that we're calling the function a few times and the results are essentially fibby, and then a call to each one of the functions.
Now this is actually happening first. It's actually allocating different copies of this function, one for each of the cases until it reaches the base case, which is fibby 1. When that happens it's going to just return the first two numbers in that sequence. Which as I mentioned, is zero and one. So after that we're using this variable sum right here to calculate the sum of the two elements. So you can see that it will add up zero and one and the result would be one.
That's what this sum says right here. And then it's going to push that into an array, and we're printing out this array right here. And then we're going to return that array. So if you look at what's happening here it's actually generating all of these copies of the function and it's getting to this one right here, fibby 1. It's adding the zero and one together, and then it's returning an array with the new one number at the end right here.
And then the result of this function is going to be fed into the previous function, which will be fibby 2, and it's going to repeat and do the same calculation over and over. This time it's going to return a new array. That one is going to be fed into the next call and so on and so forth until it reaches the last case. At the end of all that we're going to have an array that is the result of all those numbers together. Notice that the pushes aren't actually starting until it reaches the base case and those first two numbers are pushed.
Now some people love this kind of pattern because it's more elegant. Some people tend to dislike it because it can be harder to follow. I think that recursion is useful when you have a formula where calculations are dependent on previous results. Like in the case of this Fibonacci sequence. Now if recursion is a little bit hard to follow it might help to visualize it in terms of loops. So the base case is essentially when we would finish up the loops. So if you think about this as a for statement, this would be the last sort of thing that you passed to the for statement, when to exit in this case.
And then we have the recursion itself, which is the thing that keeps on repeating this series of tasks. Finally, we have what we want to do in each one of the functions, and just remember that it's sort of like a loop that runs backwards, and it's a fancier way of solving a problem. Now here are some courses where you can get some more information about how recursion work. Now as usual, if you have some ideas for this weekly series, maybe you want to share with me some questions you've been asked or have asked in interviews.
Connect with me in LinkedIn or just about any other social media network like Twitter or GitHub @planetoftheweb.
Skill Level Intermediate
Q: Why can't I earn a Certificate of Completion for this course?
A: We publish a new tutorial or tutorials for this course on a regular basis. We are unable to offer a Certificate of Completion because it is an ever-evolving course that is not designed to be completed. Check back often for new movies.