Join egghead, unlock knowledge.

Want more egghead?

This lesson is for members. Join us? Get access to all 3,000+ tutorials + a community with expert developers around the world.

Unlock This Lesson
1×
Become a member
to unlock all features

Level Up!

Access all courses & lessons on egghead today and lock-in your price for life.

Autoplay

    Create a Divide and Conquer Function in JavaScript

    Tyler ClarkTyler Clark
    javascriptJavaScript

    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

    Code

    Code

    Become a Member to view code

    You must be a Member to view code

    Access all courses and lessons, track your progress, gain confidence and expertise.

    Become a Member
    and unlock code for this lesson
    Discuss

    Discuss

    Transcript

    Transcript

    Instructor: 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.

    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.

    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.

    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?

    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.

    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.

    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.

    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.