Recursion

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 29^th, 2014