Recursive patterns – the Koch curve (iii)

There is of course a cleaner way of generating a Koch curve in a recursive manner. It involves rethinking how the curve is generated. This method of generating the Koch curve takes a input the length of the line, and how many levels to generate. In the example below the length of the line is 243 pixels, and the depth is 3. In the base case a line is drawn of a required length, otherwise in the non-base case kochCurve() calls itself four times, each time with a length one-third of the length of the previous level. In between the the four calls, the position is rotated to create the ∧ shape.

Koch curve via quick recursion

The rotations needed to create the Koch curve.

Here is what the main function kochCurve()  looks like:

void kochCurve(float lngth, int level) {
  float newlngth;
  if (level == 0){
    forward(lngth);
    return;
  }
  else {
    newlngth = lngth/3.0;
    kochCurve(newlngth,level-1);
    rotation(-60);
    kochCurve(newlngth,level-1);
    rotation(120);
    kochCurve(newlngth,level-1);
    rotation(-60);
    kochCurve(newlngth,level-1); 
  }
}

Here are the ancillary functions:

void forward(float amount) {
  float newX = cx + cos(radians(angle)) * amount;
  float newY = cy + sin(radians(angle)) * amount;

  line(cx, cy, newX, newY);
  fill(0); 
  cx = newX;
  cy = newY;
}

void rotation(float degrees) {
  angle = angle + degrees;
}

And the Processing environment specs:

float angle = 0;
float cx;
float cy;

void setup() {
  size(400, 400);
  cx = 50;
  cy = height/2;
}

void draw() {
  background(255);
  stroke(0);
  kochCurve(243,4);
  noLoop();
}

 

 

 

 

Recursive patterns – the Koch curve (ii)

The last example was a simple iterative program to calculate the first degree Koch curve. The problem is that in order to create a higher order Koch curve we would have to create some sort of deep iterative structure. That is not warranted of course, because it is much easier to do using recursion.

The easiest way is to transform the portions of the previous code which dealt with drawing the lines into recursive calls. This means modifying the way things are processed algorithmically. First we calculate the length of the line, If the length of the line is less than 5, then a line is drawn, otherwise the coordinates needed to divide the line are calculated. Each of the four line segments are then used as input to four recursive calls. Here is the code in Processing:

Code for recursive Koch curve

This produces the following Koch curve (3rd degree):

3rd degree Koch curve

The function drawKochCurveR() is called 85 times to draw this curve. It might be more meaningful to visualize this process as an infographic, depicting how one of the  four piece segments in this curve  is created (it takes 7 recursive calls).

Infographic Koch curve recursion

 

There are no 10-in-1 programming languages

Look back at the development of tools, and around the end of the 19th century tools started to appear which had many differing functions. There were loads of them, and they were heavily advertised in publications like Popular Mechanics, in the early 20th C. I’m sure they seemed like a good idea at the time. Some still exist out there in the ether, but the concept really morphed into the pocket multitool. Why didn’t the other concepts take off?

10 in 1 tool

Popular Mechanics (Jan. 1911)

The main reason these tools failed is because they tried to be everything to everyone – jack of all tasks, but master of none. The problem when you create tools like this is that there may be a hatchet on the tool, but it probably won’t function well, and may actually be dangerous… never mind the handle is also metal, and every time the blade hits wood, the shock will reverberate right along the handle.

The same is true of programming languages. There are no 10-in-1, do it all programming languages, because they just won’t do everything well. A programming language designed for visualization, might be very poor at implementing algorithms for AI, or running business apps. All languages are different and will provide you with different perspectives of programming. Don’t just settle for one language that you think will do everything. It won’t and it shouldn’t.

To learn how to program, you actually need to code

Some people think that getting into a career in computer science is a good way to make a bunch of money, and that is certainly true, but you actually have to know what you are doing. By that I mean you have to be able to program, and not just give it a cursory glance. Programming is the core building block of viable software. It goes hand-in-hand with creating viable and useful algorithms. But algorithms are useless if they can’t be implemented in some programming language. You can’t learn programming by osmosis, and unlike some disciplines where you can rote-learn things, computer science is not like that. You have to be able to solve problems. You have to be able to code. You can’t just read about code (although you should know *how* to read code), you have to experience it. You have to sit and code things, its the only way to learn. Sure, you’ll make mistakes, and you’ll learn to fix them – it’s a cyclic process. If you want to learn programming, start with a simple language like Python, Julia, or Processing. Don’t jump straight into C, or Java. Maybe take a step back in time and learn Fortran, or even Ada. Whatever language you choose, pick a simple program somewhere written in that language, and code it in piece by piece. Then make it run. Then modify it. Play with it. It’s the only way you’ll learn.

 

Recursive patterns – the Koch curve (i)

One of the easiest shapes to illustrate recursion with is the Koch curve, which first appeared in 1904 in a paper by Swedish mathematician Helge von Koch titled “On a continuous curve without tangents, constructible from elementary geometry”.

Multiple degrees of Koch curve (1 to 4)

Multiple degrees of Koch curve (1 to 4)

The Koch curve can be defined recursively using a replacement algorithm. The first part of the process of understanding how the curve is formed by means of recursion involves understanding the rules for the Koch curve, and drawing the curve on paper. In its most basic state (level 0), the Koch curve is a straight line. In level 1, the straight line segment is subdivided into three equal parts, the middle segment of which is replaced by a ∧-shaped structure composed of two segments, each of which has the same length as the middle segment, meeting at a 60 degree angle. At level 2, the middle third of each of the four line segments is similarly modified, resulting in line segments one-ninth the size of the line segment in level 0.  The process is then repeated for each straight line in the transformed line for each subsequent level. This is illustrated below:

Koch curve

Creating a level 1 Koch curve by hand

The process then moves to trying to determine an algorithm to perform the same task. The first approach is naturally a more iterative one, and requires intrinsic knowledge about the starting line, i.e. its starting and ending point. It quickly becomes clear, that although this is possible, it is likely not the best approach to drawing the Koch curve. An iterative algorithm involves deriving a list of the coordinates of each point in the completed curve, so it can be drawn, which involves a number of calculations, as new points are added, and “lines” are drawn. The Processing function below is a good example of this. 

The input to the function is the starting point (Sx,Sy), and end point (Ex,Ey) of the line, and the angle (which is set to 0 to produce the classic Koch Curve). The algorithm basically calculates the positions of the three intermediary points, than help join up the fours line segments between the start and end positions.

Here is what the output looks like when we call drawKochCurve(100,200,300,200,0):

A Koch curve of degree 1 generated using Processing.

A Koch curve of degree 1 generated using Processing.

Next we’ll see how this can be modified to produce a more recursive version to allow for higher degrees of the curve.

Here’s the setup for the code in Processing: