Fractals in Programming

Part 1: Recursion

Logan Emerson
Aug 22, 2017 · 6 min read

I’m very new to coding. So new in fact, that I’m unable to comfortably write the surely-simply code that’s required to show an example of the title of this very post, i.e. a fractal program. I do, however, have experience with fractals in mathematics and biology, and I understand that a firm grasp of the foundational concepts of recursion, terminal units, and end conditions will prove ever-useful in the ascent toward fractal programming. As such, our journey begins with a lesson in, and a coding application of, recursion.


What it Is

In the third sentence of this blog, it was written:

“I do… have experience with fractals in mathematics and biology…” -Logan Emerson

Referencing myself in this instance seems wildly unnecessary, doesn’t it? Surely this is the embarrassing mistake that ends my blogging career. Self-reference, though tactless in writing, is key to the concept of recursion. Another example of self-reference would be in Ruby class methods:

class Dog
attr_accessor :name
All = []

def initialize(name)
@name = name
ALL << self
end
def self.all
ALL
end
end

What extends recursion beyond simple self-reference is for something to be defined with self-reference. The recursive definition of recursion, as provided by the Oxford English Dictionary is “the repeated application of a recursive procedure or definition”.

What it Do

This definition doesn’t appear to be recursive, as the definition isn’t explicitly repetitious. However, the recursion is enacted by the self-reference.

Recursion is:

  1. The repeated application of a…

…ad infinitum…

… (recursive) procedure or definition.

What it Don’t

As I hope I’ve made clear, a perfect recursion doesn’t end. In a later post, we’ll work with terminal units and end states to show more clearly why they exist and, much more interestingly, how they’re determined in nature.

Cool. Let’s add math.


Numbers that Yell

Textbook: “3!”

Everyone: “Chill out, three.”

The elegance of recursion shows well when considering factorials. In text, a factorial is a number followed by exclamation point. In grade school, a factorial is “a number times each number less than it” (e.g. 4! = 4 * 3 * 2 * 1); worth noting is that the word “each” heavily implies an iterative process. In big kid math, a factorial is the product of a number (an integer, specifically) and the factorial of that number less one; this, as we now know, is a recursive definition. I promise this is cool.

First, let’s talk about (and not look at) the ugly way of calculating a factorial. Using our grade school definition, a number’s factorial is the product of that number and each number less than itself. It’s awkward to say that procedure. In Ruby (did I mention this is a blog about programming?), and perhaps in other languages, one is exposed to the concepts of syntactic vinegar and syntactic sugar. Syntactic vinegar characterizes code that looks unpleasant– code that must be able to be written with more grace. Syntactic sugar characterizes code that makes you go

We’ve got our choice between:

Vinegar, the product of a number and each number less than itself, or

n * (n - 1) * (n - 1) - 1 * ((n - 1) - 1) - 1…etc.

Sugar, the product of an integer and the factorial of that number less one, or

n!

In the shoddy visual below, the math goes down from factorial(3), then up.

I drew this freehand

First, downward:

  1. 3! ( or factorial(3) )is defined as 3 * 2!,

Then upward…

  1. 2 * 1! (which is the definition of 2!) = 2,

I mentioned “elegance”, then I drew a bad picture. This branching tree representation of 4! gets some of the beauty across:

https://i.stack.imgur.com/lz0vA.png

Things get Big, Things Fall Down

As you can see in the factorial tree, things start to get big– out of hand even– fairly quickly. This out-of-hand-ness brings us toward what’s so incredible, and ultimately useful, about fractal structures, i.e. the unique ability to fill space. What’s more, it even constitutes its own partial dimensionality (e.g. 1D lines can become 1.0–1.9D lines that exhibit some area, 2D planes can become 2.0–2.9D surfaces that exhibit some volume). This sounds spooky, but we’ll get into it.

While biologically useful, this ability to indefinitely fill space can be detrimental to one’s programming causes, because programs are only shut off by instructions, and recursive functions don’t do that unless they receive instructions to do so.

Oh God, Shut it Off

To prevent these infinite loops, we return to end conditions. Ignoring the why and the math that goes with it, let’s look at the end conditions of our two factorial methods.

Note: the initial “if” statements in the following code block may look like end conditions, but they’re only meant to check the original input of n for its integer-ness.

Without the highlighted lines, both processes would run ad infinitum, much like our above definition of a recursion.

In math, this isn’t a big deal. A graph would get very “uppy”. However, in programming, even new programmers like you and me can overwhelm our (or any) computers’ resources with singular infinite loops.

More Vinegar

To successfully calculate a factorial and break the loop using an iterative method, we used three variables (i.e. n, x, and product). Three variables for this process feels like way too many. I’d be willing to guess that my relative lack of programming skills failed me in my attempt to achieve this with two variables, but I’m certain that it couldn’t have been accomplished with only one variable; unless the function were to call upon itself, it would have no means to compare factors to verify the end condition:

17 while x <= n do

cannot be translated to

17 while (n-1) <= n do

because our iteration will never be able to terminate the process

18 product *= n-1
19 (n - 1) += 1 #=> n == n, so we loop again. And again.

More Sugar

It was, however, very easy to use only one variable, n, in the recursive method. The reason for this is that n redefines itself based on the “parent” n, modified by the method’s arithmetic. In this way, there are generations of n. Each n and its own “child” n interact to make up both factors of the product; the original elements of recursions are repurposed to continue the process of recurring in a translation of the original recursion. THIS is the syntactic sugar of recession (and thus fractals).

Here, every “parent” branch generates two “child” branches. In the next generation, those children follow the exact pattern of their parent.

So we could go with

10! = 10 * (10 - 1) * (10 - 1 - 1) * (10 - 1 - 1 - 1) * (10 - 1 - 1 - 1 - 1) * (10 - 1 - 1 - 1 - 1 - 1) * (10 - 1 - 1 - 1 - 1 - 1 - 1) * (10 - 1 - 1 - 1 - 1 - 1 - 1 - 1) * (10 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1) * (10 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1) = 3628800

or…

10! = 10 * 9! = 3628800

In Sum

Recursion on its own may seem rather bland. The applications of recursion is where the heat is. My personal favorite application of recursion is thinking about its applications to artificial intelligence: if a machine learner is recursively self-improving, what end condition is set to exit the loop (e.g. “if returns on investment diminish beyond a certain % gain for every recursion, exit loop”). In the next post, we’ll cover the classic determinator for end conditions, the terminal unit.

)
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade