Recursion Crash Course

[Music] now everyone welcome to this video on recursion so recursion is a topic that I think throws a lot of people off it's kind of notorious actually the very first teaching job I had the first interview required applicants to basically do a sample teach on recursion that was the topic that all the other instructors had decided was a good benchmark of how well how well someone can teach how could someone could teach so what I'm gonna do now is teach the basics of recursion whether you're comfortable with JavaScript or Python or Ruby recursion conceptually is the same so I'm gonna try and avoid any particular syntax I will have a little bit of JavaScript at the end to show some debugging tools what do you want but most of this is going to be language agnostic so let's get started all right so the first thing I want to explain is that for curse recursion is just an approach to writing a solution so we could have a given problem like something really simple sum up all the numbers between 1 and 100 what most of us would do are a lot of people their first instinct would be to use a loop and you could write a solution in what's known as the iterative way using iteration a loop but you could also write a solution that worked that was not iterative there's no loops involved and instead it's recursive and that's what we're gonna get into in this video how this other approach works but first let's start with a short little story so this is the way that I was taught recursion back in high school and also in college my one of my instructors did the exact same story I think it's sort of a standard computer science lesson so in like 30 seconds I'll explain it so back in some time some fantasy worlds there was a boy named Martin and an angry dragon named the dragon both symbolized by emojis here ok so one day the the elders of the village asked Martin to go up to talk to this wise old dragon and they want him to take a list of numbers for some reason and ask if any of the numbers are odd so he has this list of numbers and he's going to ask this dragon apparently the the elders he are unable to determine if numbers are odd they have to depend on a dragon to do it so he goes up with this list and he says excuse me mr. dragon are any of these numbers odd and the very angry dragon says I'm sorry boy I'll only tell you if the first number in that list is odd but that's not what Martin wants says but I need to know if any of the numbers in the list are odd not just the first number and then the dragon gets angrier and he says sorry boy I only tell you if the first number is odd only the first number in the list so Martin sits down and has a real good think he says hmm and then he has a solution he goes to the dragon he says okay what about the first number in this list and he gives him the original list and the dragon says that's not odd because it's not this even then Martin comes back with a different list he says what about this is a first number in this list odd and the dragon says nope not odd he does it again what about the first number in this list nope the dragon says it's not odd one more time not odd and then finally he comes back and says what about the first number in this list and the dragon says that's an empty list you there isn't a number in there nothing can be odd and then Martin says aha so all the numbers are even in that list nothing is odd and the dragon says I never said that so Martin starts explaining it he says well I gave you the whole list you said the first number is not odd so then I shrunk it down a bit a smaller problem I just removed that first number and I gave you a new list and I asked is the first number odd you said not odd and I kept doing this until I gave you an empty list and we know that if the empty list has nothing in it this next list had no odds for the first number had no odds that means the second list has no odds because it just consists of this number plus a new number and so on all the way up we know there are no odds and all that you told me was the first number if it was odd for a given list I just had to repeat it with different smaller lists so no odds we were just dying to know when Martin is a village hero he goes back and he lives a splendid life and the dragon smugly says you gratulations you discovered recursion and then Martin is upset he says wait you knew this whole time what is this some sort of parable for a computer science class it is Martin anyway so what is recursion though why did I do computer science instructors like to use this story it's a simple explanation of a more complicated idea recursion is just a process and when we're talking about code it's a function that calls itself over and over and over again but it calls itself which is something that if you're not familiar with recursion it can seem very odd a function calling itself but we'll get there in good time okay so here's how recursive functions work all that you do is you write a function that calls itself with a smaller piece of input each time until you reach something that we call a base case so in that example with Martin and the dragon we kept or Martin kept asking about a smaller and smaller list until we hit an empty list at which point were done so it's important to realize there has to be this base case the base case is where the recursion ends so you call a function and it calls itself and then it calls itself and it calls itself but that can't go on forever and we'll see what what would happen in that case it's called stack overflow basically it's in the recursive version of an infinite loop so there has to be a rock bottom you have to hit rock bottom everything has to stop there's a base case so those are the two pieces we have a base case and then we have a smaller input something that is getting us closer to our base case if that makes sense I'm going to show you a couple of examples that hopefully explain it in some more detail all right let's take a look at our first recursive function so it's a very simple one called countdown and all that it does is print out numbers so you pass in a number like 4 and it's going to count down so it's going to print 4 then 3 then 2 then 1 and then it's gonna print all done at the end and the first thing I'll highlight is that we have a recursive call right here so it's called countdown that's our function name and we're calling countdown inside of it second of all we have a base case which is right here and this is checking if we've hit the end of our countdown we're going to console dot log we're gonna print out all done and then return and I'll explain why that return is so important let's go run this so here I have it written up as a snippet in Chrome and I'm gonna call it with countdown pass in four as num so if I execute this we get four three two one all done let's print it out so if we step through what happens we call countdown of four and count down to four this part doesn't run because num is 4 so we console that log num so we print out 4 so we can just show that if I'm typing it this is my equivalent of console dot log then we subtract 1 from numb so numb is now 3 and we call countdown with 3 so we could basically write it this way so countdown of 3 runs this is not true because num is 3 so we print out 3 and then we call countdown again on this line after we subtract 1 from num we're calling countdown of 2 countdown of 2 is going to run this is still false so nothing happens so we console that log numb and num in this case is 2 almost there do the same thing so we subtract 1 from num it's 1 countdown of 1 ok still this is not true finally we print out 1 and then we subtract 1 from numb so numb is now 0 and we're going to call countdown of 0 what happens now is we hit the base case so we call countdown of 0 well num is less than or equal to 0 yes that's true so we console dot log all done and then we return and return is going to end our recursion because if we didn't have this return statement here our code would just continue and we would console dot log numb and num would be subtracted or be subtracted we'd subtract 1 from num and print it out and then we would call countdown again and we go into negative numbers so actually if I do remove that and you can see what happens here oh my gosh we just keep going and going and going it's not good so chrome froze to restart and I'm back now let's take a look at our second example so this one is called some range some range is going to take in a number and it's going to return all of the numbers between zero summed up until that number so if we pass in three it should return three plus two plus one which is going to be six so actually I said between zero technically it stops at one so it doesn't matter because you know you add zero and it doesn't matter but three plus two plus one or if we passed in 5 it would be 5 plus 4 plus 3 plus 2 plus 1 and the way that it works in this case we're not using a loop I'm doing it recursively so if you take a look can you identify the base case do you notice the smaller or the the different input I don't really know what to call that part the second component where we're calling the recursive call we're calling some range spoiler on this line with a slightly smaller input each time through until we hit our base case so we start out with num let's say at 3 we're going to check its num equal to 1 no it's not so we're going to return 3 the num plus summing the range of num minus 1 which would be 2 so then we're going to call it again in some range with 2 this is still false so we return 2 plus some range of 1 and this time num is equal to 1 so we return 1 so I'm going to step through exactly what happens here if you're not familiar with the call stack I have a video on this it's I only have a couple videos at this point on the channel and one of them is on the JavaScript call stack it applies to other languages as well but I think will be helpful if you watch that if you've never heard of the call stack but I'm going to step through what happens so when we call some range of 5 for example very first thing that happens this is not true so we've returned 5 plus some range of 4 so some range of 5 is added to the call stack but it doesn't know what to return yet because some range of 4 hasn't returned anything so it's waiting it's going to return 5 plus whatever we get from some range of 4 so then some range of 4 is called and that returns 4 plus some range of 3 so it's waiting and we keep going until we get to some range of one in which case num is equal to one so we return the number one so this returns one which means that some range of two can now return because it was waiting so it's um it's returns two plus some range of one which was one and then that returns so this can now return and this can return and we can get our final answer all right so I'm in the chrome debugger I've written the code up and I've simplified it to be some range of three if I execute it we get 6 3 plus 2 plus 1 and here's a little diagram I wrote up to explain what's happening when we call some range of 3 this line doesn't run that's our base case num is 3 not 1 so we return 3 plus some range of 2 so this is what's going to be returned but we're waiting on some range of 2 ok so some range of 2 is called and that returns 2 plus some range of 2 minus 1 which is 1 and that's finally when we hit our base case some range of one is called and num is 1 so this is true which means we return one so when we return 1 here suddenly this function call was waiting return 2 plus 1 we could fill in the blank so then that gives us 3 write some range of to return to 3 so then we can now return 3 plus some range of 2 which was 3 so then we get return 3 plus 3 which is 6 which is what's returned from our initial function call that's how we got 6 so if we step through this a lot of breakpoint and execute our code take a look take a look at the call stack here you'll see that the first thing that happens is some range is added that's our some range of 3 we're right here and it gets to this return return num so it's going to return 3 plus some range of 2 and watch right here you'll see we get a new some range added so this is now added on top of the call stack and you can see num is 2 in this function call so this is false we move on and it's going to return 2 plus what we have here 2 plus some range of 1 all right and you'll see another some range added to the call stack where num is now one so we're finally here and this our base case is true we have to have this rock bottom this is our end point just like with Martin and the dragon the empty list was the end point in this case it's hitting one so we've returned the value of one and now you'll see that this returns one so it's popped off the stack just a second there we go and then that means that some range of two which was waiting for some range of one can now return so it will pop off and then finally our initial function call some range of three can return and then we finally get six returned down here the last thing I'd like to do is show you a very common error that occurs with recursion called a stack overflow so this occurs when there is no base case or you don't hit the base case ever so if I got rid of this line some range is going to just continue on forever it's gonna return if we've did three it's gonna try and do some range of return three plus some range of two and so on but as soon as we hit one there's no longer a base case so that would return one plus some range of zero and then that in turn would try and do negative one and negative two and it would keep going it doesn't go forever because our our browser has a limit I think in chrome it's around 16,000 stack frames so you'll see what happens when I execute this uncut range error maximum call stack size exceeded so it doesn't actually say stack overflow in some other languages that's the actual error name or message in chrome it says maximum call stack size exceeded if I add a breakpoint again and we watch what happens if I step through this and our call stack you'll see we just keep getting these function calls added num is negative 20 20 negative 25 I'm not going to click this 16,000 times but that's roughly the number of frames that we would get and each one of these is waiting on so you know this one is waiting on this to return which is waiting on this and so on but it's never going to return a value so that's the really important part about the base case you need to have a base case in your recursive function otherwise it just keeps calling itself over and over / it's not good enough to have a smaller piece of the puzzle num - one I mean you need that but you also need to have an end point you need that rock bottom so to recap every recursive function just calls itself that's what makes it recursive it's a function calling itself and recursive function should always have a base case rock bottom as we've talked about and then there needs to be the recursive call where the function it calls itself with a different input a smaller piece usually until you hit that base case and you stop so I know that there was a lot in this video if you've never heard of recursion or you're just learning it here there's no way that you could watch one video and you know feel comfortable with it this is something that takes time even experienced developers still have problems thinking recursively it's one thing to look at a recursive solution and walk through it it's another to come up with that solution yourself so take your time this the goal of this video is not to make you an expert it's just to introduce you to the idea the concept of recursion so hopefully you can explain what it is and maybe walk through some code but it might take some more time to actually start you know writing your own recursive functions all right I'll be quiet

Channel: Colt Steele

Views: 54,725

Rating: 4.9708848 out of 5

Keywords: recursion, javascript, programming, udemy, colt steele, code, js, python, computer science, cs, bootcamp

Id: lMBVwYrmFZQ

Length: 16min 46sec (1006 seconds)

Published: Wed May 23 2018