Recursion - Part 7 of Functional Programming in JavaScript

hello in this video we are going to learn about research we are going to learn about what recursion is how to do it and why it is useful this video is also part of a series you'll get a lot more out of this video if you have watched the previous episodes in this series first you can find them there so what is recursion recursion is when a function calls itself until it doesn't that is seriously all the recursion is recursion is when a function calls itself until yes a lot of people think recursion is hard and the reason that people think that recursion is hard is that because of some collective insanity all explanations of recursion on the internet uses Fibonacci numbers as an example the only reason and non mathematician would have heard about Fibonacci numbers is if they would have watched the TV series fringe when somebody tries to explain recursion to you using Fibonacci numbers you must murder them I know that sounds rough because they they might be your friend and they are they only mean well but they must die let me draw your attention to the code we are going to implement this map count down from it should down in this case we're counting down from 10 search should just output 10 9 8 and then so forth until one stops we are going to implement this using recursion I'm going to start by declaring the function let countdown from fix our member and there's the function this is ECMO script six you might be watching this from the near future where this is completely normal to you on in current time I've had some audience requests to write things in a coma script 5 instead normally I listen to audience feedback because I love you guys but because I love you guys I won't listen to this one because I love you I want to pressure you to become better this is one situation where I won't go easy on you Eckman script 6 has been finalized for over a year now it's time to get into its really simple if you just use bobble and gab installed g4 elevator music oh boo boo boo boo boo Boop done clearing and now you can run horrible node example gasps okay that doesn't out Duncan let me oh so long this is my standard string to output run that again and we have to so quick Eggman script six crash course lead is just the new bar you should always use left instead of barn arrow functions is just a shorter function syntax hoop is cool but let's instead output the number run that okay 10 so for countdown from is a function that takes a number and starts counting down from and that is counted what counting down is you take a number say it then you take that number you just said minus one and you say that and so on until you run up so now - one run that why thank you computer for counting down to minus 15,000 if we scroll back up into infinity okay yeah somewhere here ah yeah here so you see that it works but we don't have any stop condition we're gonna fix that but I want to draw your attention to a little thing it call here at maximum call stack size exceeded the call stack it's the stack of function calls that your code has made and in most non functional programming languages there is a upper limit to how far you can go functional programming language has never had this limit because you use recursion for everything and then you can have this limit javascript has this limitation in ACMA script 5 but it is removed in Atma script 6 even though that Bobble can't simulate it because it's an engine thing and this is why atmosphere 6 is so interesting from a functional programming perspective because it removes one of the main limitations to doing functional programming with JavaScript this feature is called tail call optimization by the way because it's this big tail of function calls let's add that stop condition if num 1 0 return right so it just goes through time 10 9 8 7 3 2 1 and when it locks out 1 here and here it will proceed to this line and then it will take number 1 minus 1 and it will pass 0 in the counter from which goes into this this is 0 now we'll see that and it will return and thus it won't go to 0 and minus 1 and minus 2 and so forth until 60 minus 15,000 and that is recursion a function that calls itself until it doesn't give alight we have learned what recursion is and a simple example of how to do it but still not clear why looking at the example that we just did that you we could have done this with just a loop right and yes you could have every time you do a loop you can use recursion instead but it doesn't work the other way around because there aren't things that recursion can do that loops cannot the first time I had to use recursion was when I encountered a problem that looked a little bit like this so we had a database a relational database which had these categories so uh there was top categories like this animals category here and the top categories did not have a parent they all said no in root categories under animals there are categories like mammals if you see here that the the mammals category has animals as as parent and we have categories that have mammals as parents cats dogs and in turn there's Chihuahua Labrador which has dogs as parrot cat also cats here Persian Siamese so see that these are the same here Persian is a subcategory of cats at this time it was really cool with the this hierarchical BA dhtml menus you know menus that work sort of like the Windows Start menu where you hover a folder and when you do it expands into that folder and then you hover a subfolder that and that expands into a new subfolder and so on so I wanted to represent this database as as that so in order to represent that we need to make this in just tree structure pass to the dhtml menu we want an outfit that looks something like this boom so this is a tree structure animals contains another tree with mammals here and mammals contains to a tree with two properties dogs and cats and these in turn have Chihuahua and Labrador we don't really need modes here I think ah and since they don't have any subcategories they just have a head no its comment that out yes because this is just to remember where we're going this is by the way a good trick whenever you're programming to always so always think about what what it is you're doing what is my end goal instead of just starting to code I think one of the most common and mistakes in programming is to start coding too early take some time to think about your problem and where you're going in that will save you a lot of time scrolling up a bit and we will also I'll make three categories run that oh okay I made a mistake in my example data häringe it is supposed to be an array first curly bracket that good error here make tree is not a fun yes we have to define matrix let make tree be a function undefined yeah because make sure he doesn't return anything so yes return start by returning an empty object so now we want to start assigning the sub properties here you want to create this animals thing to do that need to break this out into a variable so we can manipulate we are gonna call this more than call back out no part so tree on hold notes in computer science we are we getting our categories from we are getting them here as and we are now going to filter the cat words array ah we are looking for the top body looking for the root element alright so this will now be a n an array of the categories that has parents and no and at this moment it will will just be this because it has filtered out all of the others because they don't have for each subcategory we are going take the ID of the category which in this case in this first loop is going to be animals here so idea here is animals and we're going to assign that to the node it's the same thing here right it's this ah and that it's now going to get the subtree uh and we gonna make that by calling make sure you recursive and it's gonna get the same categories could be some a new line but it's not gonna get the same parent it's going to get c ID okay let's run that okay that is maybe the right result it's a bit messy let me yes this is the best tarik ever json stringify and then you add as a second argument to string five you pick no and you two and two is four in divisions and now is for magic things and go now we have a nice tree and it's pretty much what we want we're still up here with the the objects but that's not that important let's look through what just happened so in the first loop when we call make tree we are passing in categories categories is going to be all of the categories and we're going filter them here I'm going to filter out the ones that have the same parent that's the one we pass in here ah and that is the same thing as what we passed in here so now it's a route ah and for every such category we are going to for each it and in this for each this is clear we're gonna unsign property on the node with the same ID as each category with animals here you can assign this node animal here with the return value of ourselves but this time we are not as me known as a parent category we are passing in animals here so now we are making a tree with the categories that have animals as approach and they in turn will pull make tree and make trees that has mammals as a parent category and they in turn will form a tree where the cats and dogs making trees that include Chihuahua elaborately and this could just go on and on and on but it ends because it runs out of things to make freezer and to a certain degree you could do this with with loops if you do nested for loops like the outer for loop has I as an integer and then the inner for loop as J and you go in and in and in until you run out of of consonants or sanity but that only works if it's a very limited amount of nesting sometimes you need to make trees that are a hundred level sleep and then you have can use use and that's recursion we have learned that the recursion is just a function that calls itself until it doesn't we've looked at an example of how to use it to count down from ten and we have looked at an example of why you need recursion why you can't solve everything loops I am the one recording is show but it is the audience that makes a show I need to hear from you either act mpj me on twitter or youtube comment down below comment with a reflection or or a question or something that you're confused about or something funny or nice or what you would like the next episode to be about speaking of which do not miss that next episode make sure that you subscribe to this channel do it now or follow me on Twitter until next Monday stay curious

Channel: Fun Fun Function

Views: 207,404

Rating: 4.9302521 out of 5

Keywords: Functional Programming (Programming Language Paradigm), JavaScript (Programming Language), Recursion, Programming Language (Software Genre), Programming Paradigm (Film Subject), Computer Programming (Conference Subject), Computer Science (Field Of Study), Software Development (Industry), Software Developer (Project Role)

Id: k7-N8R0-KY4

Length: 15min 43sec (943 seconds)

Published: Mon Aug 24 2015

Reddit Comments

[u/coffee-makes-me-poop]

Keep these coming, /u/mpjme! They're fantastic!

[u/ForScale]

Should be a video of the actual video.

[u/engid]

What is this.. an engaging tutorial, with wit and charm? Finally! I thank you, sir!

[u/Ixosis]

I was going to say, this guy looks and sounds familiar, then I realized I follow you on twitter and quora. And happy cakeday!

[u/baozichi]

I like this guy!

[u/Pantstown]

What stops the recursive call in the last example?