Month: November 2015

Best Sites for Programming Practice

Learning to code is one thing but getting better at it is another. Here are some great resources to hone your skills.
(more…)

Advertisements

Understanding recursion visually with fractals

Recursion is one of the more difficult type of concept that begginer computer programmers have to face. Simply making a fibonacci sequence doesn’t really guarantee complete understanding. Usually one has to get some experience before getting a good feel of the concept. But there’s an easier way. If you could see what happens under the hood you could get a better understanding more quickly. I found that fractals are perfect for this purpose beside being beautiful to look at.
Fractal is basically a reccuring pattern. If you zoom into an ideal fractal, you couldn’t tell how much we have zoomed in. One famous example of fractals, the mendelbrot set, is shown below.

Photo by Wolfgangbeyer

Setting up

Fractals can be drawn with ease if we have some turtle like object to draw objects. I chose to do it in C to make it a little challenging but you could use any other language you like. If you don’t understand or like the code just don’t bother and stick to the bigger details only. I used a very simple turtle structure with configurable angle and side variables. I also made some accompanying functions to serve as an abstraction layer to control turtle movement. All the code used in this post is available here in my github repo.

Our first fractal

Armed with the basic knowledge, we are ready to draw our first fractal, the Koch snowflake. It basically involves dividing a line into three( equal ) parts and then converting the middle one into a baseless triangle, repeat over and over again. In steps:

  1. Split the line into three parts.
  2. Convert middle part into an equilateral triangle without the base.
  3. Repeat the same procedure for all the new individual lines.

You don’t really need to do the procedure infinite times. We usually stop after doing it for a finite number of times. These number of times is called iterations. Here is the result of increasing number of iterations.

  1. One iteration only

koch1

At this time if you don’t get how this happened I suggest you reread the previous paragraph

2. Two iterations

This is where the fun starts. Now in the one iteration, we stop after making a single triangle but in this case we would further divide each of the four lines:

koch2But where does the base line go? If you are having this question then you must see some before I explain it

3. Three iterations

koch3

4. Four iterations

koch4

Now we can see the pattern. Instead of drawing the line first and then splitting it, the program first splits down the work down until it reaches the base case. Then it starts doing the work for all the smaller parts one by one. So the above design would be drawn from the left to the right as is without erasing any line, as we like to think about it. I know it still isn’t very obvious if you are new. One thing that could be done is to run the code in a debugger to actually see how the control flow works.

But this isn’t the Koch snowflake I was talking about. It is just a part of it. The snowflake is formed by first making an equilateral triangle and then applying the algorithm to each of it’s sides. The result is this:

kochcurve

In different colors:

kochcurve2

The Sierpinski Arrowhead

OK, that was great for our first fractal, but that’s not the only thing we could do! Another kind of fractal that we could make is the Sierpinski arrowhead. This one adds a little extra detail to the algorithm but the main idea is same as before. In steps:

  1. Draw a line( not really in case of program ). Think of the line as the base of an equilateral triangle.
  2. Move up the left side of the triangle upto it’s middle.
  3. Move parallel to the base until we meet the next side.
  4. Move down the side until we touch the base again.

Now lets get to drawing:

  1. One iteration

sier1Again read the above paragraph if you don’t really get it. Good. Now let’s move on further .

2. Two iterations

sier23. Three iterations

sier3fourth, fifth, …

6. Sixth iteration

sier6Wow! did you see that coming? We started with a simple rule and got an unexpected result. But if you look closely, You will see that all the smaller parts of the curve are the same as in iterations 2.

In different colors:

siercolor

This is the power of recursion. The basic idea is that you can apply the same algorithm to the larger thing and it’s individual parts with ease. Recursion is used frequently in computer like quick-sort, merge-sort, graph searching, towers of Hanoi… and making beautiful fractals. This is just the tip of the iceberg. You can find fractals everywhere in nature. Even in your body!( the blood vessels ). You can find more about them on the Internet if you like( there are also tutorials teaching how to make the Mandelbrot set mentioned in the start ).

Credits

I got the idea for this post from an exercise of the book Think Python. I picked the name “pica” for the turtle from the book Squeak: Learn Programming with Robots