Fractals and Self-Similarity
A fractal is an object or image that exhibits
self-similarity – self-similarity being the quality of “having a substructure analogous or identical to an overall structure” [1]
on all scales. Perhaps the most straightforward example of a fractal is a
simple line segment. It is a fractal because every sub-segment of a line segment is a smaller scale version of the
whole, no matter what part of the line is being considered. Fractals have
fractional dimensions. In theory, this
means that they are not regular one, two, or three-dimensional things, but
rather, actually have dimension between
one and two, or two and three! There
are many fractals in nature, for example Romanesco broccoli, as well as man
made fractals, such as the Sierpinski gasket and Koch’s curve.
Fractals can be
made by taking some kind of base shape and applying and reapplying the same
change or set of changes to it, ideally ad infinitum, but usually only a very
large, though ultimately finite number of times. In other words, they can be
made by applying a recursive pattern.
Any fractal “can be defined in terms of
itself.”[2]
As such, we can write code that is similarly “defined in terms of itself”, i.e.
programs or functions that call themselves within their own implementation, to
create representations of certain fractals on our computers. This kind of
self-calling code constitutes recursive programming.
Recursion in General
When a problem can be broken down into
smaller but identical or analogous problems, we can use recursion to solve it. In
computer science, “recursion means ‘defining
something in terms of itself’ usually at some smaller scale, perhaps multiple
times, to achieve your objective.” [3]
In Python, the reality of a program being “defined in terms of itself” is a
little funny looking and counterintuitive at first: A function that is
recursive calls itself. This may seem
not to make sense at first blush, since, if we are in the middle of a function
definition, how can we use the function that we haven’t even finished defining
at that point? This is perfectly valid in Python and most programming languages,
however. All it tells the computer to do is to pause and start applying the
function to the problem on a smaller scale before continuing – where “continuing”
may also include this kind of delving into smaller scales to various degrees. Basically,
“recursion is induction that can be carried out by a computer.”[4]
In this way, it is a very human side to programming. Usually, the result is, we
computer scientists being able to solve highly complex problems with much
simpler code.
[1]
http://www.thefreedictionary.com/Self-similar
[2] How to Think Like a Computer Scientist: Learning with Python
3 18. Recursion (http://openbookproject.net/thinkcs/python/english3e/recursion.html)
[3] How to Think Like a Computer Scientist: Learning with Python
3 18. Recursion
(http://openbookproject.net/thinkcs/python/english3e/recursion.html)
[4] Professor Danny Heap, in lecture, January 29th,
2014
