Algorithms in JavaScript
Create a Divide and Conquer Function in JavaScript
Divide and conquer (or D&C) can take some time to comprehend. It is composed by using recursive functions to create a base case and to divide or decrease a problem until it becomes the base case. Let’s create a D&C function to accomplish a task with JavaScript
Instructor: [00:00] When working with Divide and Conquer, it's important to understand that these types of algorithms are recursive algorithms. Divide and Conquer isn't a simple algorithm that you can apply to a problem.
[00:09] Instead, it's a way to think about a problem. When faced with a problem, you can think, "How can I divide or split this problem down to its simplest form?" Recursion empowers this mentality, because it requires a problem to be able to broken down into sub-problems, and then returns or solves them up from the bottom.
[00:28] Let's create a function -- we'll call it sum -- that takes an array. We'll say let total equals zero, for let i of array, total plus-equals i. Then we'll return our total. Now, we'll console.log our sum, passing through an array of one, two, three, four, five.
[00:47] Perfect. We see that gives us 15. We are simply just looping through each item inside of our array, and plussing it onto each other, which gives us 15. How could we use Divide and Conquer and recursion to break this down into smaller problems?
[01:02] Let's first think about, what is the simplest case with our numbers? If we had an array of just one number, or even an empty array, that would be pretty easy to sum up. It would just be zero or that one value. This is our base case. Our goal is to move closer to this with each recursive call.
[01:21] In order to remove an element each time we recursively call this function, we first need to make sure we're adding up that removed item to the remaining state of the array. We'll do that by slicing off the rest of the array, and then adding it to the first value of the array.
[01:38] Recursion is a first-in, last-out. Our function on the first return call returns a one-plus sum array, two, three, four, five. Then within that function, we're returning a two-plus sum three, four, five. It'll continue to do this until we reach our base case, we return zero.
[01:57] Which is then added to the last number, five. Then it's five plus four, which makes it nine plus three. 12 plus 2, and finally, 14 plus 1, which gives us our value of 15. Recursion is nice because it keeps returning our new state after each function.