Recursion Crash Course: Learn Recursion in 15 minutes with JavaScript

hey it's lee halliday and today we are going to learn all about recursion we're going to solve six different problems using recursion and in the process learn some of the ins and outs of it so we're gonna start nice and simple we're gonna start where we're basically counting down from five to one so um that's basically the basis of recursion is to repeat something until you're done so you always have sort of those two ideas of repeating something and then knowing when to finish that repetition and the way we repeat something is through recursion basically doing the same thing over again but with a variation of it so let's get into it so our goal is to call this function here countdown and it's going to output console.log 54321. so if we were to just plop a console.log in there with the number and then come over here and run it so we get five those undefined ignore them they're for problems we're going to solve in a second um what we need to basically do now is know do we want to keep counting down or have we reached the bottom so what we're going to do is we're going to check if the number is greater than 1 that means we want to keep counting down so after 5 since we're going down our next number would be 4. so what we want to do is basically call countdown again that's the recursion basically you're calling yourself you're calling the same function you're already in but we want to go with 4 so we're going to say num minus 1. and then it's going to come up here with 4 output 4 and then it's going to count to 3 to 1 until it runs out so we run this again and we count down to 1 and then we're done so i'm going to comment this out so we just don't have that output messing us up and now we're going to go on to the next problem where we're summing an array of elements so here's the array of elements we have here and it adds up to 15 so we want to try to do this without sort of using your typical iteration like for each um or reduce or something like that so what we want to do here is basically let's first check have we reached the end so what we're going to do is we're going to say if the elements dot length is 0 we are going to return 0 as sort of the last the last response you always need a way to end your recursion so you always need this check see how we add an if statement if statement there's basically always an if statement in recursion so if we get down to this point we basically know that we need to keep counting so what we could do is we could put it in an else but because this returns you you don't need it but we'll just keep it here so what i want to do is basically take the first number in here and then add a sum of the remaining elements so we're going to split these out and we're going to call this the head element and then the rest is equal to the ellums and then what we can do is we can return the head plus a sum of the rest and this is going to keep iterating and keep sort of reducing the size of our array until it doesn't exist anymore so if we run this we get 15. but just for a little bit more visual um visual output let's console.log the elements as we're iterating over them and we're changing the value that we passed to the recursive call so we run this and we see that it starts out full and then it it's missing the head then the head of that and then eventually you get to an empty array and the reason i return zero is because it will basically at this point it's like 15 plus 0 sort of thing because the the last when you pass an empty array that's when it stops the recursion okay so let's get rid of the console.log let's comment this out and move on to our next problem so here we're going to basically calculate the power of something so 2 to the power of 2 4 to the power of 4 that sort of thing so i think 4 to the power of 4 is 256. so we're going to try and solve this and basically what we're going to look for is we need to know when we want to stop calculating the power so we're going to say when our power is equal to 1 what we're going to do is just return the number so let's imagine this what's 4 to the power of 1 that should just be 4 which is the num here so if i were to run this we get 4. but we have to handle what happens if you pass 4 to the power of 2 which would be 16. so we didn't handle this at all let me just clear that okay so in our else portion here we need to basically say we want to return the number times the power of that same number this time one less so if it starts out as the power of 4 or the power of 2 we would want to say to the power of that minus 1. so that it keeps counting down until it gets to 1 in which case it just returns the number itself so if i were to run this 4 to the power of 2 is 16 if i increase this to 4 to the power of 4 we get 256 so that's how you can use recursion to calculate the power of something next problem okay factorial so factorial is when you see like five with an exclamation mark but what it means is you do five times four times three times two times one so it's the same counting down which we've seen a few times so far so what we need to do is basically know when have we counted down long enough basically when are we at the last one so we'll just say if the number is we could say when it's equal to 1 or we could say when it's less than or equal to one if that's the case we're basically just going to return one as our final sort of here you go multiply this whole thing by one which would be this last one here so else this is where we're going to do the recursion so what we want to do is we want to say let's multiply the number so imagine we're starting out as five we're passing five here we're going to multiply the number times the factorial of the number minus one so whenever we call it we're always modifying it a bit otherwise it's never going to end in which case this thing that kicks us out of the loop will never execute so by doing this factorial of 5 is 120 which is what you get when you multiply these numbers together i think let's try with factorial 2. that would be 2 right and we'd change it to 3 which would be 3 times 2 is 6 times 1 is 6. cool so it seems to be working that's how you do factorials with um recursion comment that out and move on to everyone's favorite thing that you never have to actually do but everyone uses for for teaching recursion fibonacci kill me now i hate fibonacci i'm sure he was a good guy but still okay the way fibonacci works is basically when you've got a string of numbers these two numbers added together give you one then one plus one add together is two one plus three added together is three so it's always the previous two numbers equal what the next one is in the sequence so here we would have 8 plus 13 which gives us 21. so we want to calculate in this case the sequence of 15 fibonacci numbers so let's actually start a little bit simpler and we're going to say give me the fibonacci sequence of 2 and in our case it's 0 and 1. so what i've actually done is i've initialized this array um basically if you don't pass the second argument here the accumulator or like how many numbers we've calculated so far is going to start as 0 and 1. so we're sort of cheating a little bit but what we're going to do is first handle our edge our end case so if the remainder is less than or equal to 2 we're just going to say return the accumulator so if we were to run it here boom fibonacci solved to two places perfect but if we say three places we're screwed now because it doesn't return anything so we need to handle the else and in that case i need to grab the the previous two elements in the array so if we're trying to calculate 21 we would calculate these two so what we're going to do is basically call fibonacci again but first we want to get what are the two numbers previous in this accumulator so we will say we've got the second last one and the last number is equal to slicing the accumulator array basically stripping off the last two and then destructuring them to get them into a variable so now what we're going to do is we're going to return the fibonacci of how many um sequence numbers we have remaining so remaining minus one and then we're going to pass along our accumulated value here so what we basically want to do is take our accumulated value and splat it in or whatever that thing's called and then add one more number so that would be the second last times the last gives us our new last number so let me just there we go so if i were to run this now it doesn't work what did i screw up all right let's figure this out we've got rem minus one so this would be two and then it would return our accumulator second times last is the last two oh i know why i'm an idiot okay i was multiplying them together and the reason it's zero here is because i was multiplying uh zero times one which is zero you add them together not there we go now we have beautiful fibonacci take that up to 15. there we go so that's how you calculate fibonacci using recursion so i think the next example we're just going to comment this out is probably the coolest one and it's basically how you can do operations on trees of data so like a parent that have children and those children might have their own children which might have their own children so you can't really iterate easily over those because you don't know how many levels deep you're going to need to go so instead what you do is you do recursion to basically just handle one level of that tree at a time so this is the data we've got working with and it's basically the species data of coffee so everything started out from the arabica bean and then from there you have heirloom and bourbon and so heirloom has children i just didn't record them so bourbon has two children that i've recorded katura and mocha and then we've got another type which is a child of arabica which is typica and it's got kona and java so basically each level of the tree has a node and then that node's children which could be just an empty array so we call this by passing in our root tree and we've destructured this here to basically have the node in a variable and then the array of children so what i want to do is just output the node so we'll just run this and we get arabica so what i want to basically do now is iterate over the children of arabica so i'm going to say if children dot length is uh greater than zero that means we want to iterate over we don't really need an if statement because you can just if there's nothing in the array you can you just don't have to iterate but what we're going to do yeah screw this maybe it won't work but but we'll see what we're going to do now is we're going to take say children dot 4 each and then for each child what we are going to do so remember a child is itself a tree so because it's a tree as well we're going to call print again with the child so now when we run it we get both sort of the ultimate parent and then heirloom and then we get bourbon and its children and then typica and its children but it'd be nice if it sort of indented each level of that and here's a cool little trick so instead of using console.log change it to console.group so if i were to run this basically it just for each group it indents one level but you can see here it sort of forever indents so that's useless so what you do is you basically tell the console when the group has ended so here we're going to say when the node has ended call this so now what you get is a sweet tree printing out where we have arabica and its children on this level and then we have katura and it's no children from then on so in just a few lines of code we've iterated this tree structure of data using recursion so yes we did iterate over this this array using the typical for each but that's fine because inside of each one of those we recursively called ourselves with a smaller portion of the tree and basically the the loop is stopped here when children is an empty array because in that case there just won't be anything to for each over so it won't keep sort of going down deeper and deeper levels that was it that was recursion in a nutshell i hope you enjoyed it and you can recurse some many functions all right take care bye

Channel: Leigh Halliday

Views: 1,842

Rating: 5 out of 5

Keywords: recursion, fibonacci, factorial

Id: sVJkE_Z_CDM

Length: 15min 42sec (942 seconds)

Published: Tue Apr 20 2021