Recursion and marking a rule (i)

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.

rulerEG

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.

ruler

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.

rulerACT

Recursive algorithm trace

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.

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.