Recursion and marking a rule (ii)

The code in the last post creates the ruler in a particular way, i.e. it marks the middle, then processes the left, and then the right of the middle. This could be called pre-marking. If we wanted to change it up, and use in-mrking, we could put the call to mark() in between the left and the right recursions. This really does nothing to detract from the end result, as the order the marks are drawn is irrelevant. It just offers another way of posing the recursive solution.

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

To get a simpler ruler than the previous example, let’s try rule(0,128,4), which will result in 15 marks on the ruler. Here is the outcome:

ruler4

The recursive structure can be represented by a recursive call tree. This diagram has a node for each call to function ruler, containing the parameters that are passed to it. The children of any node correspond to the recursive calls to ruler within that function instantiation. A tree diagram can be used to illustrate any type of recursive algorithm. Here is a recursive call tree for rule(0,128,4).

rulercalltree

Recursive call tree.

The other thing the recursive call tree does is to allow divide-and-conquer algorithmics to be visualized.

 

 

 

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.