THE COLLEGE HILL INDEPENDENT


Beyond Our Fingers

The Hidden Beauty of Recursive Computing

by Dash Elhauge

Illustration by Eli Neuman-Hammond

published October 2, 2015


 

When I was four, I snuck into my mother’s bedroom and flicked the switch by her makeup desk. Big filaments blazed around the frame of the mirror. Blinking and wincing, I gripped the faux-silver handle of one of her hand mirrors and slowly turned it.

As a child, I’d always suspected that beyond the mirror was another world—and with it, another child who felt as close to me as I to him when his fingers were cool against the mirror. But when I turned my mother’s mirrors toward each other, there wasn’t one child, but hundreds. Some of them seemed to be standing far in the distance, smiling shyly, others close with their fingers outstretched.

I knew then that the other child who’d touched my fingers through the glass was a trick of the eye. I felt alone, but still connected to some property I didn’t quite understand. I placed my eyes in front of the mirror and watched them collide and spin like an all-seeing vortex. No matter how sneakily I popped up between the mirrors, I appeared, again, like a stacking self-consciousness that obliterates into the infinite.

Two mirrors pointed at one another is known as an infinity mirror, and is a direct result of recursion. A few years later I began computer programming, which makes regular use of recursion, in part to chase what I’d found in my mother’s bedroom.

But what seemed odd to me then—and what seems odd to me now—is how most of us can see the beauty in the recursion of an infinity mirror, but few of us can see it in computers. 

 

+++

 

Recursion has two components: a base case, a predefined beginning of a sequence, and a recursive step, which defines each subsequent state in the sequence in reference to a previous one. In the case of the mirrors above, I was the base case because I existed independently of the mirrors. Reflection was the recursive step because it generated a new copy of me each time it occurred. After several iterations of reflection, a visual pattern emerged that made the recursion clear even to little four-year-old me.

In the case of the mirrors, the recursion was easy to see because so many copies of myself were made and each one was almost exactly like the previous. But when recursion has more drastic changes during the recursive step, or is only performed a few times, the pattern can be difficult to recognize. Furthermore, certain types of recursion can produce complex sequences that make the fact that they’re recursive even more difficult to realize. This dissonance in complexity—that a set of simple recursive rules can lead to something elaborate—is a powerful property that often yields beautiful results.

The Game of Life is a prime example of this. Devised in 1970 by British mathematician John Conway, Life begins with an n-by-n grid. A player is told to choose whichever squares in the grid they’d like to be considered “alive.” The player has no intervention from that point on (causing some to argue that Life should really be called a simulation). As the game starts, it goes through a series of cycles, following four simple rules:

  1. Any live cell with fewer than two live neighbors dies, as if by underpopulation.
  2. Any live cell with two or three live neighbors dies in the next turn.
  3. Any live cell with more than three live neighbors dies, as if by overpopulation
  4. Any dead cell with exactly three live neighbors becomes live, as if by reproduction.

Life became an instant smash hit in a broad number of fields, especially computer science. Coinciding with the release of inexpensive minicomputers, tens of thousands of hobbyists began running simulations from home. They quickly discovered Life had incredible computational potential. For instance, one could fill out a series of cells in Life to create an “addition machine,” so that if you filled a particular set of cells in a way that indicated you had the numbers 3 and 5, over time another set of cells would become alive to indicate the number 8. In fact any computation that’s performed on computers today can be performed within the context of Conway’s Game of Life. Even more amazing is that because Life can perform any computation performed on a computer, and Life is run on a computer, Life can be simulated from within Life—the ultimate recursive game.

Mathematicians Alonzo Church and Alan Turing had posited decades earlier that all computable functions could be expressed as recursive functions. For example, consider natural number addition. The process of addition probably seems so simple now that it’s hard to imagine it simplified, but if you ask a preschooler to perform addition between two boxes of beads, they’ll probably proceed the following way: they’ll count all the beads in one box, and then individually move each bead from the second box into the first box. As they do so, they’ll add one to their count. This is recursive: at each recursive step, a bead is moved from one bucket to the other, and at the base case there are no beads left in the second box. This primitive version of addition is easier to explain to a preschooler than the abstract version with which we are now all familiar.

This process of abstraction is why computer programmers are able to create complex systems. Computers are stupid. Way more stupid than preschoolers, because (most) computers don’t learn. As a result every single little operation a computer performs needs to be hard coded. But if someone who’s constructing say, a website, needs to think about how exactly your computer allocates RAM every time they sit down to code, they’re going to go crazy—the same way you’d go crazy if you had to think about the minutia of petroleum combustion every time you pressed the gas pedal on your car. Computer science relies on levels of abstraction, and recursion provides a way for us to simplify functions, like addition, that are too abstract for a computer to understand. The fundamental power of recursion­—creating something that appears complex through simple means—may be the key to its beauty.

 

+++

 

Martin Gardner wrote in Scientific American in 1970 that “The [Game of Life] made Conway instantly famous… because of Life’s analogies with the rise, fall and alterations of a society of living organisms…” Biologists and mathematicians noted how easily large stable lifeforms organized themselves given only a few simple rules. Three classes of lifeforms arose: “still lifes,” which manage to maintain one stable shape, “oscillators,” which cycle through a few shapes every few iterations, and “gliders,” which give the appearance they are “gliding” through the game. The game has a resulting beauty that seems deeply embedded in our conception of what it means for something to be alive. Life’s organisms appear to have desires, to try and survive, to recreate. Some sets of organisms even form symbiotic populations. When organisms cease to be, others feel their loss. There seems to be an inherent connection between recursion and nature.

In the 12th century, the Italian mathematician Leonardo Fibonacci wanted to predict the growth of rabbit populations. Fibonacci suggested we think of an initial population of two baby rabbits, left in the country to be checked on once a month. After the first month we come back and the babies are all grown up, and we feed them some carrots and they twitch their noses in that adorable way that bunnies do. The next month our bunnies have done the nasty and now we’ve got another pair of bunnies. And the next month, they’re at it again, and now we’ve got two pairs of adult bunnies and one pair of baby bunnies. What we’re left with is a simple recursive formula: the number of pairs of rabbits in each generation is equal to the sum of the number of pairs in the previous two generations. Today, this pattern is known as the Fibonacci sequence, and it serves as the basis for the Fibonacci Search Algorithm in computer science, a powerful method for searching quickly through lists.

The Fibonacci sequence, as it turns out, pops up all over nature. Lilies, buttercups, roses, and ragworts all display petal counts consistent with the Fibonacci sequence. It should be no surprise, then, that there is an inherent beauty in the Game of Life.

But some dissonance still seems to exist here. The computational potential of Conway’s game and the potential for life seem to be intertwined as a result of recursion. So why don’t computers and smartphones, which have nothing but computational potential from recursion, feel intertwined in the same manner? 

 

+++

 

The Droste effect is perhaps the most intuitive version of recursion. Named after a popular Dutch cocoa powder from 1900, the effect occurs when a version of an image is embedded within itself. The original box of Droste cocoa powder featured a nurse in one of those pseudo nun uniforms that nurses apparently wore in the early 20th century, carrying a box of Droste with a picture of herself on it. Today, the recursive structure of computers makes creating the Droste effect easy. By taking a screenshot of a window of a screenshot several times, anyone can create the effect on their home computer. 

The graphic artist MC Escher used the Droste effect in his drawing, The Print Gallery, in which a man looks upon a picture of a ship. When we examine the image closely, we can see a small art gallery by the shore of the ship. In that gallery is the same man we’re looking at, looking at the same picture. And what’s in that picture? Nothing. Escher doesn’t bother to continue the pattern ad infinium because to do so wouldn’t make a difference. We can’t see anything that small, so why bother drawing it? Escher realized that recursion’s beauty has perceptual limits. Only on certain scales for certain functions is seeing recursion intuitive.

Another example where recursion is intuitive is fractals. If we draw a line with two branches, and then give each of those branches two branches half the size of the previous branch, and keep doing this for awhile, we generate a “tree” structure, with an inherent symmetric beauty. Which brings us back to our initial question­—why does aesthetic beauty seem to pop up in every version of recursion in this piece except for computers themselves? 

The answer, I think, is that the abstract nature of recursion’s beauty is also its downfall. As recursion becomes more and more extreme, humans cease to perceive it. In the case of the iPhone, for instance, there’s so much recursion on such radically different scales that we don’t understand it at all. Just like a computer scientist, we must abstract ourselves from the device to be able to use it. Though a pointer finger swipe down on the iPhone may involve more recursive elements than Escher or the fractal, that doesn’t make it beautiful.

But that won’t stop me, of course, from thinking of a world beyond my fingertips every time I check my email.     

     

DASH ELHAUGE B’17 is Dash Elhauge ’16 + 1 gap year.