Divide and Conquer

What is Divide and Conquer?

Divide and Conquer (D&C) is a well-known recursive technique for building algorithms. Essentially, D&C takes a problem and continually breaks it down into smaller pieces while applying the algorithm to each piece and combining the result into the final solution.

A Visual Example

Let’s divide a rectangle into the largest, equal squares possible.

• the boxes are not square

• the boxes are not equally sized

• the boxes are not the largest they can be

Enter D&C

There are two steps to using D&C to solve a problem and because it uses recursion, the steps are the same:

1. Identify the base case - the simplest possible case
2. Decrease/divide the problem into smaller sets until you reach the base case

Step 1

In order for the square to be of a size that would fit in the larger rectangle cleanly, the square needs to have sides that are multiples of one of larger rectangle’s sides - 400x240. This is the base case.

Step 2

• Find the largest square that can fit into the rectangle
• We’re able to fit one 240x240 square into the larger rectangle
• Are one of the sides (240x240) of the remaining space a multiple of the one of the largest rectangle’s sides? No
• Continue

Step 3

• We repeat the algorithm on the remaining set
• We’re able to fit one 160x160 square into the remaining sub-rectangle
• Are one of the sides (160x160) of the remaining space a multiple of the one of the largest rectangle’s sides? No
• Continue

Step 4

• We repeat the algorithm on the remaining set
• We’re able to fit one 160x160 square into the remaining sub-rectangle
• Are one of the sides (160x80) of the remaining space a multiple of the one of the largest rectangle’s sides? No
• Continue

Step 5

• We repeat the algorithm on the remaining set
• We’re able to fit one 160x160 square into the remaining sub-rectangle
• Are one of the sides (160x80) of the remaining space a multiple of the one of the largest rectangle’s sides? Yes!
• The largest square that we can use to totally cover a rectangle of 400x240 is one of 80x80

A Code Example

Let’s sum an array of numbers - [3, 9, 2, 7, 6, 5]. Using a loop is pretty easy and straight forward:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func main() {
    var sum int

    for _, n := range []int{3, 9, 2, 7, 6, 5} {
        sum += n
    }

    println("sum:", sum)
}

/*
sum: 32
*/

Run in Go Playground

Using Recursion

Step 1

Identify the base case. Seeing as how we’re working with an array, what is the smallest array that you can have? If you said an array of either zero or one elements, congrats :)

Step 2

Identify/create the recursive case. We need to progressively reduce the problem set. One way to do that would be as follows:

From the base case, we recursively sum the value from the previous sum function with the next value in the array.

The Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func main() {
	arr := []int{3, 9, 2, 7, 6, 5}

	var sum func(xs []int) int
	sum = func(xs []int) int {
		if len(xs) == 1 {
			return xs[0]
		}
		return xs[0] + sum(xs[1:])
	}

	println("sum:", sum(arr))
}

/*
sum: 32
*/

Run in Go Playground

Fin.