Hello, friends. I'd like to talk to you about something near and dear to my heart. Have you found recursion?

Now, recursion is nothing to fear. It's actually a neat trick that can make for some clean code. Instead of ugly loops that can take several lines, you just make a neat little call to your own method within itself with one line.

For example, we're all familiar with the printing a triangle example. The one where you make a method that prints out a triangle of symbols, like asterisks, like this:


    *
    **
    ***
    ****
    *****
  

We can approach this method two ways. The first way is with a loop. Observe:


def print_triangle(rows)
  count = 0
  while count < rows
    count2 = 0
    while count2 <= count
      print "*"
      count2 += 1
    end
    count += 1
    puts
  end
end

No offense, code, but you're looking kind of chubby there. And the two very similar variables that have very similar tasks can be kind of confusing. We can cut down on the loops by doing the following:


def print_triangle(rows)
  if rows > 0
    print_triangle(rows-1)
    rows.times do 
      print "*"
    end
    puts
  end
end
  

What is this code doing? First, it checks if our input is greater than 0. If it is, that means we still have something to print, and that means we have to call our method again with an argument that is one less than our previous one. We'll continue this cycle until we reach zero, at which point, nothing happens in the current method, it just ends. Once that ends, though, the focus returns to where the all of the previous method calls left off, starting with the most recent. In this case, the most recent call was to print_triangle(1). Following the single loop, that will cause 1 * to be printed, followed by a new line. Next, print_triangle(2) will be called, which will cause the loop to print * twice, followed by a new line, and so on.

But that seems needlessly complex for such a small method, doesn't it? Just a parlour trick? Maybe in this case. But you have to admit, it's pretty cool.

Then when can we use recursion? And when should we?

We can use recursion whenever we have a problem that can be broken down into similar incrementally smaller problems. Like in our print_triangle example. We needed to print increasingly smaller lines. We accomplished that by first establishing the base case, which is VERY IMPORTANT. Without the base case, your recursion will go on forever. In this example, the base case was 0, because there were no more asterisks to be printed at that point.

Ok, so that's when we can use it. When should we use it??

It should be used when it can cut down on the time your code needs to run significantly. This happens most famously in the case of exponents. Let's say you need to make a method that takes in two numbers; one number as the base, and the other as the exponent. We can do it the old-fashioned-loop way like this:


def power(base, exponent)
  count = 0
  result = 1
  while count < exponent
    result = base * result
    count += 1
  end
  return result
end

What's wrong with this block of code? Technically, it does what we expect it to do. A call to power(2,2) returns 4 in 0.1 seconds. A call to power(2,3) returns 8 in 0.1 seconds. A call to power(2,200000) returns an incredibly high number after 2.8 seconds. A call to power(2,2000000) makes my computer give up. Too bad, it would have been a long time. But those 2000000 loops made it's head explode. It can only do so much. You know, sometimes you just need a high exponent, and when you do, what can you do?

Let's apply some recursion to this bad boy. It's pretty obvious that this problem can be broken down. power(2,3) is saying multiply 2 by itself 3 times. We can break it down in one of two ways. First, for demonstration purposes, we'll break it down one by one with the following:


  def power(base, exponent)
    result = 1
    if exponent >= 1
      result = base * power(base, exponent-1)
    end
    return result
  end   
  

Hmmm... Technically, it works, but it's only a little shorter than the first attempt. But it's still the same number of loops. Testing gives us power(2,3) is 8 in 0.1 seconds. Uh-oh. Testing power(2,200000) tells me my stack level is too deep, meaning my computer's head blew up again.

And what exactly was the point of that? To show you that recursion doesn't automatically make things faster. Not only did we have the same number of loops for the code to iterate through, we also made the computer go through the trouble of instatiating the method object each time. Ouch. Poor thing.

So what is a person who needs a large exponent to do? Well, recursion really is the answer, we just need to use the most effective kind. The kind where we cut the loops down by half each time we call our method again. In our previous method, we only decremented our exponent by 1. Keep in mind everything you know about exponents and watch this magic:


  def power(base, exponent)
    result = base
    if exponent > 1
      if exponent % 2 == 0
        result = power(base, (exponent)/2) * power(base, (exponent)/2)
      else
        result = base * power(base, (exponent-1)/2) * power(base, (exponent-1)/2)
      end
    end
    return result
  end
  

Now what is this code doing? Knowing what we know about exponents, 24 can be broken down into 2² * 2². 26 can be broken down into 2³ * 2³. We take advantage of that, and use recursion to find the answer of half of the exponent, and mulitply that times itself. (Note that in the event of an odd exponent, we have to multiply the result times the base one more time.)

That's all well and good, but does it work? A call to power(2,3) returns 8 in 0.1 seconds. A call to power(2,200000) returns a veeeeery large number in 0.2 seconds. And a call to power(2,2000000) returns...... a very successfully large number in 5.2 seconds. We did it! We got the computer to compute a very large value without exploding after too many iterations!

So to recap, recursion can be used when your problem can be broken up into incrementally smaller mini-problems with the exact same type of input, and you have to remember to always set a base case to break the cycle. Also, if you can cut your base values by half, it is very very very worth it to use recursion. Otherwise, it's just a cool trick that's just as good as looping. But still cool!

Wow. It just now returned a call to power(2,20000000) in 156.8 seconds. Not bad for a call that killed my computer with the two previous implementations. Also, it took me that long to write that last paragraph.

Anyways... So welcome recursion into your heart. It can save your computer from the eternal flames of crashing from too many iterations.