Jacques Mattheij

Divide and Conquer is a name given to a group of algorithms that take a problem and then solves it recursively (recursion is a programming concept where a program uses a simpler version of itself, a bit like those Matroshka dolls). For instance, there is a very elegant algorithm that sorts lists of elements like this named Quicksort.

But that’s definitely not the only interpretation of those words. Historically they came from ‘divide and rule’, the concept of getting the locals to fight with each other which allowed a common enemy to rule them. United we stand and divided we fall…

The reason why I think that divide and conquer is the most powerful strategy in programming is that it can be applied on a higher level: while writing complex programs. If you are faced with a task that is too difficult to solve in one go you can apply the divide and conquer method stepwise until the problem you have to solve is a trivial one. Then you back up one level and re-apply until all the sub-problems are solved and this in turn solves the ‘too complicated to solve’ problem that you had in the first place.

Even more powerful: this applies to all problem solving, even outside programming. Let me give you an example: Need to remodel a house? Too complex to oversee in one go and for sure if you just start without a plan you’ll get stuck and/or depressed and you’ll burn down your house. No need for that! Break it down and it all gets a whole lot easier:

• infrastructure
• electricity
• gas lines
• water lines
• heating
• rooms
• kitchen
  • do ceiling
  • prepare walls
  • tile floor
  • place cabinets
  • place countertops
• bathroom
  • do ceiling
    • place wooden lattice
    • screw giprock
    • mudding and sanding
    • paint
  • prepare walls
    • tile walls
    • tile floor
    • place shower base
    • place shower doors
• bedroom1
• bedroom2
• livingroom
• attic
• basement

I’ve detailed a few entries further to show that you don’t need to stop at any particular level, you can subdivide as far as you want. This is an extremely handy trick, it allows an individual to solve almost any problem given enough time. It applies equally to repairing cars, troubleshooting electronics learning and so on. There isn’t a task that I can think of where ‘divide and conquer’ does not make that task easier and it always surprises me when people either don’t know about it or do not know how to put it into practice. And if you do the dividing job before you start the actual work your divisions automatically become the plan which makes it usually a lot easier to spot what could go wrong and/or what the proper order is to do things in. For instance: in the example above it is now painfully obvious why you should do the floor before you place the cabinets in the kitchen which can save you costly time and money as well for re-work.

Obviously there are some classes of problem where the strategy will fail. If you wish to lift Mount Everest by your lonesome then you’re not going to get very far even if you manage to somehow break it up into ‘two roughly equal halves’. But that’s because the task itself is beyond the reach of any single person or even humanity. But for most problems we are faced with on a day-to-day basis the rule holds that you can usually break them up into simpler or smaller problems.

So the next time when faced with something that you can’t do, either in computer programming or simply in the real world: Divide and conquer! Break the problem into two roughly equal pieces if at all possible, then try to solve those and if they are still too big repeat the process until at least some portion of the larger problem becomes tractable. Even slicing one small portion of the problem makes the remainder easier to solve.