What Is Recursion - In Depth

recursion is one of the most confusing topics in computer science but it's used everywhere in programming so in today's video I'm going to be simplifying recursion for you and if you're new to the channel make sure you subscribe for more videos where I simplify the web for you let's get started now now Before we jump into any crazy code examples using recursion we first need to understand what recursion is and luckily the definition is very simple the idea of recursion is a function that calls itself that's it all it has to do is call itself somewhere inside of the function and immediately you're probably thinking that you just run into an infinite loop of a function calling itself over and over and over again until your computer dies of the world explodes but the thing about recursion is that it works a lot like normal loops and then you have some kind of exit condition that jumps you out of the recursion so that the function stops calling itself over and over again and the thing that makes recursion difficult to wrap your head around is you have to keep track of all the previous calls inside of the recursion stack when you're trying to plan out a recursive function so what I'm gonna do in this video is we're going to take a look at a few examples of normal non recursive functions and then we're going to change them to be a recursive function so I can show you the difference between the two and we can also visualize what's going on to start with we're gonna cover the most basic example which is a function that counts down from the specified number you give it all the way down to zero so let's just take a look at this basic function all we have is a simple for loop that counts down from my number as long as we're greater than zero it's going to subtract 1 each time we go through the loop and it's just going to print out that number and we'll only get to 0 it's just going to print out hooray so let's call that function we're just going to say count down and let's say that we give it a 3 it's going to count down as you see 3 2 1 and then hooray let's just clear out our console and let's work on implementing this as a recursive function and now remember in a recursive function instead of using a loop like this what we're going to do is we're going to call the same function over and over again so let's create that function we're going to call it here count down we're just gonna call it count n recursive so that we can separate it from our other function and again it's going to take a number n that we count down from and the first thing we need to do in a recursive function is we need to have our Clause that breaks us out of the recursive function so in our example here we are going through this loop as long as I is greater than 0 which means we are breaking out of this loop when I is less than or equal to zero so we need to do it here is we need a check if n is going to be less than or equal to zero then we want to break out of our recursive function and to do that we just call the return statement but we need to actually call this console dot log hooray inside of here as well because this is what's going to happen at the very end of our recursive function just like this happens at the end of our loop after we break out so now we have a break out statement which is essentially the exact opposite of the wild condition for our for loop then we can actually implement the recursive nature of our function and the important thing is if we forget this our function is just going to call itself over and over and over again and tell your browser in this case chrome crashes which is something we don't want so now let's go down here first thing we want to do is do our console dot log when we print out in because in this case we're printing out our member here and then the next thing we need to do is we need to call our function again but what do we pass into this function here well up in this loop you can see we're subtracting one from I which means we're just constantly making our number n smaller by one so what we doing here is we're gonna pass n minus one into our countdown function now we're just gonna save that and see if this actually works so let's call countdown recursive of three and you see it prints out three two one and a hooray so this works exactly the same as our typical countdown function but let's break it down a little bit further to figure out exactly how this function works so we're going to break this down step by step the first thing that happens is we call countdown recursive and we call it with the number three and what this is going to do is is going to go into our loop it's going to say is three less than zero it's not so we skip all this we're gonna log out three and then after that we're going to call countdown recursive with n minus 1 which in our case is 2 this is done inside of countdown recursive so we're gonna say countdown recursive of 2 and again same exact thing is n less than zero no it's not ok so we're going to call this countdown function again countdown recursive but this time with 1 and then again same thing it's not less than or equal to zero so it's going to call again countdown recursive and this time it's going to call it with zero and now immediately we come in here and we see oh it's less than or equal to zero so we return so here is what we do we're returning out of this statement we're now no longer in this countdown recursive zero and now we move up back into countdown recursive one and our countdown recursive one is already at the bottom of the function so it just returns because essentially when you reach the bottom of your function it's like having to return at the bottom just like this so we leave countdown one go back to countdown to which starts right here again it's at the very end of our function because it just finished calling this so we go back to countdown three and again it's at the bottom of the function so it leaves it again so all of these are returning themselves so it look kind of like this we do our return and then we do our return and our return for all these different functions that were calling just like this so that's kind of how this really basic recursive function works but as you note it's not really very useful to make this recursive it's so much easier to do it in a loop and it just makes more sense easier to wrap your head around so let's look at another example of a recursive function one where we actually are taking an input and constantly growing our input inside of our recursive function which is something that's very common in most recursive functions so here's another example of a very common iterative approach that we would take to a solution to some a range of numbers so if we get the number 3 in here we want to sum 3 2 & 1 together which will give us 6 so all we do is we initialize our total to be 0 we loop through all these different numbers starting at our highest number going all the way down till we get above 0 subtracting 1 each time and adding it to our total and then we return our total at the end so let's test this function we can call some range of 3 as you can see we get 6 which is just 3 plus 2 plus 1 now let's work on iterating this in a recursive function so we just create a function down here which is going to be called some range and this is going to be recursive and instead of here we're again going to take the n value which we're passing into our function and as you can see the very first thing that we're doing here is we're creating a total variable and setting it to 0 but since we're inside of a recursive function any variable we set in this function is only available to that one single version of the recursive function and not to all of them so we need to pass this total value to all of our different recursive functions and by default the first time we call this function we want our total to be set to 0 by default so now that we have that out of the way let's create our guard clause which is going to exit as out of the function immediately so again we're going to say here this is while I is greater than 0 which we leave our loop when I is less than or equal to zero so we can just say when n is less than or equal to zero we want to exit out of our loop we want to return our current total otherwise if we are not inside of that guard cause we want to do here is we want to return our total which is going to be plus and that's going to be our new total here and we also need to call this function so it's called some range recursive and we have our total version right here which is going to be our total plus our current number but what is our end going to be our n is just going to be n minus 1 which we're going to pass to our function here and it's emulating here our looping of just subtracting 1 every single time so now let's save that and call this function sum range recursive of 3 and you see we get 6 it's working as intended but let's deep dive again into how this function is actually working let's go down here and the first thing we're going to do is we're gonna call some range recursive which 3 and that's just going to essentially default our total to 0 even though we don't have to pass that in and inside of here we check is our number of 3 less than 0 it's not so we're calling the exact same function again and this time it's going to have to and for the value for the total is just going to be 0 plus 3 which in our case is going to be 3 here now let's move on to the next iteration which is it's going to be the exact same function again but this time we're calling it with a number 1 and our total here is going to be 5 because it's 3 plus 2 again 1 is not less than or equal to 0 so we're calling this function on another time it's going to be our last time because we have now an N of 0 and our total here is going to be 6 so now we can go back up we can say ok n is less than or equal to 0 so what we want to do is we want to return our total which in our case is 6 so what this is going to do is it's going to return 6 and now we jump back to our some range recursive with the 1 and 5 and it's right here at this point we just executed the code here so we're returning whatever this function returns in our case that's returning 6 so this function is going to return oops return 6 and again go back up when we call some recursive 2 and 3 it's going to return from this function and it's going to return whatever that function returns which in our case is again just going to be 6 and as you can imagine the very last function we call here is going to do the same thing it's calling this function and what this returns is what this function is returning to for us which is six so as you can see the functions that we've covered so far are just easier to do with a for loop they make more sense that way and that's perfectly normal recursion is not something you use all the time but the next function that we're going to be covering is something that you almost always need to use recursion for because it makes your code so much easier to follow so let's look at that now so here we can see our function which is called print children and as you can see there's no implementation for it because they do this with loops as I said is incredibly complex and almost impossible and what we want to do with our function is we want to take this tree here and we just want to print all of the children all the way down as deeply nested as they go so if we for example past this tree we have John which has the children Jim and Zoey and then we also want to print Zoey's children which is going to be Kyle and Sophia and to do this with a loop as I said is difficult so let's look at how to do it with a recursive function which is actually pretty straightforward so let's create that a function which is just going to be print children recursive and again it's going to take whatever tree we want to pass into it and the very first thing we need to do is we need to create our guard cost to exit us out of the loop so we're going to say if our tree which in our case is T dot children oops children dot length is equal to zero so if our tree for some reason has absolutely no children in it we just want to return and this is going to prevent us from here when we get to Jim or Kyle or Sophia it's just going to exit out because we don't have any children to loop through the next thing that we want to do is actually loop through all the different children so we can just say T dot children dot for each and for each child that we have inside of here we actually want to run some code and the first thing we want to do is just print out that child so we can just say child that name instead of here to print it out and then we want to loop through all of that child's children so we can say print children recursive and we can pass in that child and that's all the code we need to write here let's just save this and execute it to make sure it works we're going to pass in that tree variable that we have and as you can see it prints out Jim so Kyle and Sophia and as you can see down here at the children are Jim Zoey Kyle and Sophia so let's again deep dive into how this code actually works let's make a little bit of room for ourselves and the first time that we call this we're going to be calling print children recursive and this is going to be with John's children so we're just gonna put in John here and when we get into this we see that John has two so we're actually going to be calling this function twice we're going to be calling print children recursive with the gym and we're going to be calling it again a print child recursive whoops recursive and this time it's going to be with Zoey so let's first look at how gyms call gets executed we can see that Jim has absolutely no children so this is just going to return it's not going to do anything inside of here so we don't really have to worry about that branch too much and now it's going to move on to this zoey branch and as you can see Zoey has two children so again we're gonna call this function print children recursive two times one time is going to be called with Kyle and Kyle's children and the next time is going to be called here with Sofia there we go and both of these don't have any children so again they're just going to return and they're going to return and now Zoey is going to return after going through all of her different children and then John is lastly going to return when he goes through all of his different children just like that and now let's even look a little bit deeper into this so as we can see we call this with John we go through here he has children so we don't actually execute this so we loop through each one of his children print their name and call it so the first time we come through here we call this on Jim so we completely ignore all of this code down here with silly right now we just called this with Jim and we go through Jim's children so we see that Jim doesn't have any children so we exit immediately and then we can move on to our next function which is the one with Zoey so we come in here we see that Zoey does have children so we loop through each one of them and the first thing we do is go through the first child which is Kyle and we jump into this again and return because it doesn't have any children and so on as we go through Sophia and the rest of them and eggs out and as you can see if we close this off save it and recall that function of print children recursive with our tree you can see that that is working properly and is something that as I mentioned is very difficult to do iteratively with a normal loop because you don't know how deeply nested these children could be they could be nested two levels deep like this or they can be nested 100 levels deep so writing that with an iterative loop is just much more difficult than this simple code here to print it out recursively and that's the real benefit of recursive functions over iterative functions and that's all there is to recursive functions make sure to check out my other videos linked over here for more simplified explanations of web development also subscribe to the channel if you enjoyed this video and want more videos like this thank you very much for watching and have a good day

Channel: Web Dev Simplified

Views: 55,200

Rating: 4.9715099 out of 5

Keywords: webdevsimplified, recursion, recursion javascript, recursion tutorial, recursion explained, what is recursion, how to use recursion, why use recursion, recursion tree, recursion examples, recursion for beginners, leran recursion, recursion in depth, recursion guide, recursion programming, recursion explanation, recursion javascript tutorial, recursion javascript example, recursion javascript explained, recursion easy, simple recursion, recursive, recursive function

Id: 6oDQaB2one8

Length: 13min 25sec (805 seconds)

Published: Tue Jun 11 2019