Source

3 simple steps for writing recursive methods in Ruby (or any other language)

When I first encountered recursion in programming, it totally blew my mind. The idea that a method could call itself made no sense at all to me. After all, if a method can call itself, would it not just keep running on forever?

Worse yet, look at the code below: a simple recursive method that takes an integer as an argument, then adds it together with every previous integer stopping at0.

def add(n)
  if n == 1
    return n
  end
  n + add(n - 1)
end

Do you see on the second to last line where the method is calling itself again? Now, imagine that n = 10 and try to evaluate the method in your head. It went something like this for me…

OK, first I skip past the if..end statement because n does not equal 1. So far so good.

Next, I take 10 and add that to add(n — 1)

But wait, I need to know what add(n — 1) evaluates to before I can add it to 10, right?

So 10 + add(10 + 1) would actually be 10 + add(9)

But in order to figure out what add(9) evaluates to, don’t I need to evaluate the entire add(n) method over again? And won’t I just run into the same problem again when I try to figure out what the next level deeper evaluates to??

How can I ever figure out what value to add to 10 when that value is the result of a seemingly endless number of nested equations that I have to figure out??!

Remain calm

Wrapping your head around recursion takes a while. It’s one of those things that you have to keep coming back to; exposing yourself over and over to different variations and use cases. It’s one of those times in life where you think you’ve got it all figured out, then you encounter a new implementation you haven’t seen before and it knocks you right back down the ladder.

Worry not though, as even computers blow their stack when they attempt to run a recursive function that goes too far down the rabbit hole.

For example, If I run the recursive method above on my MacBook Pro, I get a ‘SystemStackError’ when I provide any integer higher than about 10,000 as the argument. If a computer can’t figure it out either, don’t beat yourself up too hard in the beginning!

Fortunately, there are some reliable strategies that can help you write recursive methods, even if you don’t totally understand how recursions works yet.

Step 1: Write a non-recursive method

Let’s build on my previous example. Here are the requirements again:

Write a method that will accept any positive integer and return the sum of that integer, plus every previous integer, ending at 0.

Setting the method aside for a moment, if we were write out this expression starting with the integer 10, the calculation should look something like this:

10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 55

With that in mind, let’s start writing our method. Start by defining the method. We’ll call it #add:

def add
  # code will go here
end

Next, we want to isolate just a single iteration of the equation above, one that captures the change that occurs from one step to the next. In this case, we are stepping down by 1 at each iteration of the equation, so isolating one step of that might look something like this:

def add
  10 + 9
end

Now, how would we express an equation like 10 + 9 in terms of a variable n if n = 10? That would look something like this:

def add(n)
  n + (n - 1)  # => 10 + (10 - 1) => 10 + 9
end

If we ran this method now, passing 10 in as the method argument, we’d get this:

10 + (10 - 1) = 19

And that’s it for Step 1! All we needed to do was isolate a single iteration of the written out expression and then represent that expression in terms of a variable n that we pass into the method.

If you think about it, it kinda makes sense. After all, recursion is really just a loop that runs the same method over and over and over again. So if we can capture the essence of the mutation that occurs at each step of iteration, then that’s all we need. The looping nature of recursion will take care of the rest!

Step 2: Create an exit strategy

Every recursive method needs a cue to stop repeating, otherwise it will continue on forever, eventually crashing your program. The idea here is to identify the last meaningful iteration of the loop, then make that the out clause. This is also referred to as the ‘base case’.

Going back to our earlier equation, it looks like 1 is the last meaningful number we could possibly add to our total. Adding a 0 would be pointless, as it would not change the end sum, and we know from the requirements that we’re not going to be dealing with any negative numbers.

10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 55

Knowing this, we’re going to add an if..end statement to our method that triggers only when the last meaningful value is detected. We still want to include that value in our calculation though, so we simply make it the return value.

def add(n)
  if n == 1
    return n
  end
  n + (n - 1)
end

The idea here is that once we hit the final meaningful run through the method, we want to return the last meaningful value and no longer invoke further recursive calls.

It’s also important to point out that we should place this ‘out-clause’ at the beginning of our method so that it gets checked first, before any other code is run. The reason for this is that if we accidentally include our recursive method call before the out-clause, there may never come an opportunity to execute the out-clause.

On to the third and final step!

Step 3: Add the recursive method call

The only thing left to do now is to add in the recursive call. After all, it wouldn’t be a recursive method unless the method called itself somewhere within itself right?

Determining where to add the recursive method call isn’t always straightforward and it will ultimately depend on what exactly your method is designed to calculate. However, in most cases, there are a couple simple rules that can help guide you:

1. The recursive call(s) will most often be found in the return value of the method, with one exception: You will never find a recursive call in the ‘out-clause’. Remember, that’s your way of stopping the recursive calls.
2. Recursive functions will typically use the argument that was passed into the method (n in our case) as part of the new argument for the recursive method call. Because we want each successive trip through the method to bring us one step closer to the out-clause, the argument n that we’re passing into the recursive method call will usually modify the original argument in some way towards that end goal.

Armed with these guidelines, we should now be able to reason out where we want to add our recursive method call.

Knowing that the return value of our method is on line 6, we can assume that’s where to want to look first.

1  def add(n)
2    if n == 1
3      return n
4    end
5
6    n + (n - 1)
7  end

And knowing that our recursive method call is likely going to be wrapped around the part of our expression that gets us one step closer to our ‘out-clause’, we can reasonably assume that it should likely be associated with the (n — 1) expression. If you subtract 1 from our starting integer enough times, n will eventually trigger our out-clause right?

1  def add(n)
2    if n == 1
3      return n
4    end
5
6    n + add(n - 1)
7  end

With the method complete, let’s try running it in Ruby’s REPL tool, IRB…

We know from writing out the full expression that our answer should be 55 (when we provide 10 as the argument). And 55 is exactly what we get. Woo hoo! Success!

Final thoughts

Recursion is a tricky subject to grasp, and it will most likely take some time for you to fully get comfortable with. However, if you follow the 3 step process I’ve provided, it should at least bring you at one step closer to proficiency with recursion and total spiritual enlightenment.

If you have any questions, or examples of other recursive functions you’re stuck on, let me know in the comments below and we can explore them together. Even better, if you’re a total pro at recursion and you have some additional tips (or corrections) that could further help me and the other readers advance our understanding of recursion, please share those too!

Thanks for reading and happy coding!