Hilbert Curve and Recursion

As was mention in a previous blog the Hilbert curve is a continuous space-filing curve.

It is also categorized as a fractal. A fractal, according to the fractalfoundation is a never-ending pattern that is infinitely complex and is self-similar across different scales.They are created by repeating a simple process over and over in an ongoing feedback loop.

Usually, fractals take an exact example of themselves and repeat it over and over to create this pattern. In terms of Hilbert Curve, a simple U shape is repeated to create the curve. As noted by datagenetics, “an easy way to imagine the creation of a Hilbert Curve is to envisage you have a long piece of string and want to lay this over a grid of squares on a table. Your goal is to drape the string overboard so that the string passes through each square of the board only once. The string is not allowed to cross over itself.”

This constant looping of the initial pattern brings us to the topic of recursion.

Let’s Talk Recursion

For recursion to occur an algorithm needs to call upon itself, repeating the initial process once the previous is completed.  Recursion may be hard to grasp but let’s look at some examples of recursion in nature. The Nautilus Shell and Fern leaf are perfect examples of recursion in nature. In the shell below the section in the spiral is an exact repeat of itself but at a larger scale outwards. As like the fern that comes from a branch, that then branches individual branches that then branches leaves.

Here is another example of recursion occurring a man-made object: The Russian nested dolls. Every time a doll is opened an exact replica of itself is on the inside.

Recursion Russian Dolls
Russian Dolls: Recursion occurring with itself.

There are many other fractals that demonstrate recursion. Some popular ones are the Koch Curve (View sample code), Dragon Curve(View sample code), Sierpinski Triangle (View sample code) and Carpet, Lévy C Curve and much more.

Next post we will look at the Hilbert Curve more in-depth.

References:

Advertisements