Recursion / by Becca Barton

Recursion. It's a fun word. But what is it?

A quick explanation is that it's a clean way to perform a repeat task on an element that is continuously breaking that element down into its most basic parts in order to reach an end goal.

The longer version goes like this: Say you have something you're passing into your function via an argument, and you know you want that information to be manipulated within the function. So you have your starting information, and a clear idea of what the final information should be. You know you could use a loop to manipulate the data until it reaches the certain end condition, but you also know that a loop could take many lines of code. Enter recursion. 

Recursion is useful when you're faced with the dilemma of trying to perform the same action until the variable meets a certain condition, but you're not totally certain how many iterations it's going to take you to get there. 

It is, essentially, setting up a loop. So why doesn't it just keep going on forever and ever? The key to recursion is that eventually, every problem is broken down into its smallest possible part, known as a base case. On each iteration, the the problem is being broken down into a simpler version of itself, until it finally reaches the simplest version of itself. By setting up an if condition, 

When I first came across this in programming, it sounded like a foreign concept. Calling a function within itself? It sounded less like a way to solve a problem, and more like a way to break your terminal. Outside of coding, though, we actually encounter recursion all the time. Think of a tree: it starts out as one large trunk with many large branches, but follow any given branch out, and you'll find that it breaks down into smaller and smaller pieces, until you've eventually reached the smallest twig at the very end. It even happens in lightning (see: cool GIF on the right).

So how does it work? Setting up a recursive function has a few criteria. First, there must always be a defined base case. This is the most basic, simplest possible form of the data. Think of Russian nesting dolls— the starting point is the biggest doll, and on every iteration through, you're dealing with a smaller and smaller version of the doll until you eventually have broken it down into the smallest, most basic form, which is the tiniest doll.

(Re)curse With Caution.

Another important thing to keep in mind is that for every problem that can be solved recursively, there's also a way to solve it iteratively, through a loop. The benefits of using recursion include it being a bit more elegant and concise. After all, you've already written the code to perform the exact function you want— why not reuse it?

The downside to its implementation is that because it's calling itself, it's adding a new series of requests to Ruby's performance stack. This means that typically, recursion is going to be a slower way to solve a problem than implementing a loop. Knowing what your priorities are beforehand (eg. readable code? faster performance?) will help you decide which route is the best for your problem.

It's an elegant way to avoid eating up twenty lines of code setting up a complex set of nesting loops. It's also a great way to impress your programmer friends. The key thing to remember: recursion is great, but there's a time and a place for it. If you're looking to create clean and elegant code, go right ahead and use it. If, however, your main concern is speed, use with caution.

Okay, so how would YOU use it?

Kinda like this.

Kinda like this.

Recursion can be used in a lot of different ways. Here's my dream program for using it. Anyone who designs has probably spent a fair bit of their time sifting through their font library trying to pick the perfect font. A little bit of recursion could be used to solve this dilemma.

Say you're creating a design and need to pick the perfect typeface. Opening up FontBook, you can see you have about 500 options. Now, you could go in manually look at each of the 500 versions, or you could use recursion to separate all of your fonts and return the useful ones to you. Imagine a program that does this heavy lifting for you, eliminating options and just returning the relevant ones.

You need to sort this unwieldy list of hundreds of fonts into a much more manageable one. Nobody has time to sit there and type out 'partyhats' in 600 fonts. Instead of setting aside a Saturday and manually organizing all of your fonts into nice lists, let's stop and consider that we're programmers, and we can use programming to solve this problem.

Each font can have many categories. It can be sans-serif (lineale) or serif, but also geometric, or humanist, and it can also have different feelings (elegant? quirky? assertive?).  Imagine a program that would divide this one gigantic list of fonts first into a few basic smaller ones— serif, sans-serif, script, and slab-serif. Now instead of one complicated and category-filled font list, we've separated it into multiple simpler piles. This isn't simple enough, though. Next, we want to further sort each of these piles into even smaller, simpler versions of themselves, using their specifications. For example, we want to look through the sans-serif pile and assign each font into either a humanist, geometric, gothic/grotesque, and neo-grotesque. For serifs, we want to split each pile into smaller piles of old-style, Didone, and transitional (we could get into an argument that slabs belong in this category, but let's just agree that slab-serifs deserve their moment in the sun). From there, we can separate further into any number of categories, such as feel, time period, etc., depending on what your preferences are. 

This program works by using recursion to take one large problem, and breaking it down on every iteration into smaller and less complicated versions of itself. We eventually end up with a collection of base cases, or fonts sorted into their respective piles. We want the program to keep running until each font can't be sorted anymore, but we aren't sure how long this is going to take because we don't know how many categories each font has, or how many fonts the user will have. Recursion takes care of both of these unknowns by sorting the fonts until they just can't be sorted anymore, as opposed to sorting them a certain number of times. 

To finish up our ideal font sorter, we'd also like to see the program take in parameters from the user, including the categories they'd like to explore and a test phrase, and return a given phrase in each of the fonts from the list that best matches the criteria of the user.

If you'd like to start developing this with me, hit me up.