Recursion is kind of like the cloud – it’s hard to explain and you might not ever see it, but it definitely is a thing. Yet we deal directly with recursion more than we may realize.

Recursion is the process of repating a procedure or action. In Ruby, we put all of our procedures inside of a method, and we use loops to repeat those procedures again and again. So, if we have methods and loops, what’s the need for recursion?

Well, as Rubyists, we’re pretty lucky to work with a language that’s intuitive and human-friendly. We like to read and write code that’s actually comprehensive and (ideally) can be understood and appreciated by programmers and non-programmers alike. It turns out that recursion is a big part of that. It can make our code more readable and can even help it run faster.

Functionally Recursive Babushkas

In Ruby, we use recursion when we call a method from within itself. Sometimes, when you’re within the scope of a method, you want to repeat the same action again from inside of it. Functional recursion achieves exactly that goal.

One of the best metaphors for recursion that I’ve heard comes from my friend and fellow classmate, Jimmy. He explained recursion as a set of nested Russian matryoshka (aka babushka) dolls:

These dolls work in a pretty interesting way. Within each one, there is another doll that is exactly the same. You have multiple copies of the same doll, each within another, until eventually, you get to the smallest doll.

In the programming context, the smallest doll is your base case. The base case is imperative when it comes to utilizing recursion. It’s how you tell your recursive method when to stop calling itself from inside of itself.

Imagine what would happen if you didn’t have a final doll to end with – you’d just keep going and going and going until, eventually, your head would probably explode:

Or, more likely, you’d be stuck in something like an infinite loop, and you’d eventually use more memory than whatever was available to you in the stack, ending up with an error like SystemStackError: stack level too deep or Stack overflow!.

These kinds of errors are good reminders of how dangerous recursion can be. But don’t let that dissuade you! Recursion can also be pretty powerful, especially if you want to repeat a function multiple times.

Recursion, Rinse, Repeat

A classic example for explaining recursion is calculating factorials. Just in case you need a refresher: a factorial is the product of an integer and all the integers below it, up to the number 1. The factorial of 4 would be written out as: 4 * 3 * 2 * 1, or 24.

Now, we could very easily write this using a while loop:

1
2
3
4
5
6
7
8

def factorial(num)
  factorial_count = 1
  while num > 0
    factorial_count *= num
    num -= 1
  end
  puts factorial_count
end

But let’s look at this code for a second. What exactly happens when our compiler runs this code? Well, a lot of stuff.

1. First, it has to keep track of our counter, since we only ever want to calculate a factorial down to the number 1.
2. Then, it checks that the number being passed in as a parameter (for example, num = 7), is greater than 0.
3. If num is greater than 0, it will multiply num by the counter.
4. Then, it will decrease the counter by 1.
5. Finally, it repeats steps 1-4 again until num = 0, in which case it will and finally break out of the while loop.

Okay. WHUT?! This seems like a lot of stuff to keep track of. And that factorial_count variable is pretty weird and counter-intuitive (pun totally intended). And if we were calculating the factorials for a larger numbr – say 70, instead of 7 – this would be a lot of logic to keep track of and repeat over and over.

Let’s rethink this problem for a second. What we actually want to do is find the factorials of all the numbers smaller than 7 and greater than 1, and then just multiply them together. In fact, all we really want to do is repeat the same procedure of multiplication.

Instead of using a loop, we could write a method that takes in a single argument num, and actually use that same method to replicate the process of multiplication. That might look something like this:

1
2
3
4
5
6

def factorial(num)
  if (0..1).include?(num)
    return 1
  end
  num * factorial(num - 1)
end

There’s something pretty interesting happening here. If we pass in the number 7 as our parameter for num, our compiler does the following:

1. First, it immediately jumps past the if statement.
2. Next, it multiplies 7 by factorial(6)
3. Then, inside of the factorial(6) method, it circumvents the if statement again, and multiplies 6 by factorial(5).
4. Eventually, when it hits the if statement, it returns 1.

Here’s a visualization of what this looks like:

1
2
3
4
5
6
7
8

factorial(7) = 7 * factorial(6)
             = 7 * 6 * factorial(5)
             = 7 * 6 * 5 * factorial(4)
             = 7 * 6 * 5 * 4 * factorial(3)
             = 7 * 6 * 5 * 4 * 3 * factorial(2)
             = 7 * 6 * 5 * 4 * 3 * 2 * factorial(1)
             = 7 * 6 * 5 * 4 * 3 * 2 * 1
             = 5040

Does the Russian doll metaphor make a bit more sense now? Here are our seven dolls, each one nested within another. And our base case is 1, which is where our nesting and recursive function actually ends, helping us avoid a stack overflow error.

I think that the best part of this code, though, is that it’s a lot easier to read. There’s no counter, no loop, no incrementation. Just one clean and crisp method that you can use as many times as needed after defining it only once. And, if you think about it, the visual representation of the compiler’s actions mimics exactly how a real human would write out and solve a factorial problem.

One of the most difficult aspects of programming is picking the right tool for a job. Sometimes, that tool might be recursion and make your job easier. Other times, it might be the completely wrong choice and infinitely complicate your life. But, the more that you code and get comfortable with recursion, the better you’ll be at recognizing when to bust out the recursive wrench out of your toolbelt.

tl;dr?

• Recursion is the process of calling a method or function from within itself.
• Functional recursion must have a base case in order to avoid stack overflow errors.
• Still curious? Check out this video, which introduces Ruby recursion in great depth.