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”.
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:
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):
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: