Divide-and-conquer is a classic problem solving strategy, with the idea being that a problem is divided into two, and those problems are divided etc. until a solution can be derived. In the context of recursion, divide-and-conquer involves two recursive calls. These type of recursive divide-and-conquer algorithms do not reduce to a trivial loop, as in the case of the Factorial, nor do they lead to excessive recalculation, as experienced with Fibonacci, because there is usually no overlap in data. As a simple example, consider the task of drawing the markings on a rule. Markings (imperial) are generally of a different size, depending on whether a mark represents ½”, ¼”, ⅛”, or 1/16″. The resolution of the rule is basically ½^n, so ½^4 will provide a resolution of 1/16.

The code (written in *Processing* for ease of visualization), uses a function **mark(p,h)** to make a mark **h** units high, at (horizontal) position **p**. The middle mark should be **n** units high, the marks to the middle of the left and right halves should be **n-1** units, etc. The function **rule(l,r,h)** determines where the marks are to be positioned, and operates through the use of binary recursion. The three parameters represent the left bound (**l**), the right bound (**r**), and the height (**h**) of a mark.

void rule(int l, int r, int h) { int m; if (h > 0) { m = (l+r)/2; mark(m,h); rule(l,m,h-1); rule(m,r,h-1); } }

The first call to the function, say **rule(0,128,6)**, makes a rule from 0 to 128 in length, with a height of 6. The 0 relates to the left bound, the 128 to the right bound. In the first iteration, m is calculated as (0+128)/2 = 64. A mark is then made at position 64, of height 6 (note this is scaled in the actual function **mark**, as shown below). Then rule calls itself twice: rule(0,64,5), and rule(64,128,5), dealing with each side of the middle.

The idea is that to make the marks, first make the largest mark in the middle. This divides the rule into two equal halves, and the marks in the small sections can be made in a similar fashion. The recursion terminates when the length of a mark to be made is 0. Here is the result of the above recursive run.

How does it work from the perspective of recursion? Let’s look at a small example. If we try and trace through the algorithm for **rule(0,128,4)** on paper, we can see how each mark is made, and how the recursive calls to **rule()** are activated. The example below shows working through the left half of the rule.

Now here is the rest of the Processing code:

void setup() { size(260, 75); // Set the size of the sketch-board background(255); // Set the background colour to white fill(0); // Object fill colour = black smooth(); noLoop(); } void draw() { rule(0,128,4); saveFrame("rule4.png"); } // Function rule goes here void mark(int pos, int ht) { line(pos*2,50,pos*2,50-4*ht); }

P.S. A rule and a ruler are basically the same thing. What may differentiate them is that a rule measures straight from its edge; a ruler on the other hand starts its measurement a little way in from the edge.