Recursion Simplified

Why write an article about recursion? Every developer already knows what it is and it’s taught in every single computer science course the world over. Still, it’s a technique that can have even the most experienced developers running to the hills. There is a good reason for this; in whatever aspect they choose to deploy their skills, most developers will have no cause to use recursion and in many will have a really good reason not to. Over time this lack of exposure leads to an unfamiliarity and, eventually, rabid and uncontrollable fear.

The reason I am writing about recursion (well, the boring reason anyway) is that I’m planning to do a few articles about search algorithms and those will use recursion fairly liberally, so I wanted a foundation article to refer back to should anyone be afflicted by this rabid and uncontrollable fear 🙂 However, it dawned on me that I may have some wisdom to impart in the process of doing so. Therefore the aims of this article are to answer the following questions;

1. What is recursion?
2. Why are people so freaked out by recursion?
3. How can those people shed their freak-out-ed-ness?
4. How do you use recursion?
5. When should you use recursion?

I used to struggle a bit with the concept myself. I eventually was lucky enough to have a very logical approach explained to me by a man named Uday Reddy around ten years ago – suddenly everything was so clear. Hopefully I’ll be able to do the same for you guys. Examples will be in C#

What is recursion?

Well, lets start off with a silly example; Go ahead and type “recursion” into google. You’ll find yourself presented with your search results along with a familiar message asking you;

Did you mean recursion?

Of course I did! A quick click on google’s advice leads me to the same page, with the same question. Aaaaah. I see what they did there…

Wikipedia, at time of writing, cites the example of two mirrors positioned exactly parallell to one another as an demonstration of real-world recursion. Already then, we’re associating the concept of recursion with the concept of infinity. Keep that in mind while we head straight into another silly example…

One of the available alternatives to XML is YAML (used for configuration files under the Ruby on Rails framework, for example). YAML syntax is significantly different to XML syntax in a number of ways; of particular note are the importance of whitespace and the complete absence of <braces>. In fact, it has almost nothing in common with any markup language so how very dare it acronymically declare itself “ML”? Well, it’s for this very simple reason;

YAML stands for “YAML Ain’t Markup Language”

Aaaahh, I see what they did there as well. Another recursion gag.

So why are people so freaked out about it? Well, anyone who directly or unknowingly subscribes to Knuthian programming principles believes that their code should read like a good novel. Somebody should be able to visibly see the thought processes that went into constructing any piece of code, even if they were not the author. When was the last time you read a novel that went on forever, or instructed you to go back and read a bit that you’ve already read?

In going through these examples, we’ve stumbled upon the very reason that most programmers will avoid recursion like the plague if they can: Basically because it messes with your head; The human brain can’t really comprehend the concept of infinity and it’s something that makes people go “aaaaah” in the context of a gag. Why on earth would anyone want to introduce complex and ridiculous factors such as these into their code!?

Well, the first thing to make clear is that the word recursion has a very different meaning when applied to computer science. Here, recursion is used as an adjective to describe a function. To give it a really sterile definition, a recursive function is one that “calls itself”.

Let’s just bin the concept of infinity straight away – all function calls go on a stack and a stack can overflow, ergo a recursive function needs to stop somewhere. Secondly, you shouldn’t ever just use recursion for the sake of it – there are very specific cases where it is appropriate and outside of those cases it is rightfully guilty of its own major criticism: it makes your code less readable.

In those situations where it is appropriate, however, recursive code can actually be far more readable than any for-loop powered equivalent. It is my personal belief that recursive functions are only “less readable” when they’re used in inappropriate situations – hopefully I’m about to convince you of the same thing.

How to think about recursion logically

In a nutshell, recursion can be summed up as follows;

If a problem domain is vast, but a simpler version of the same problem would be easy to solve, then it makes complete and total sense to simplify the problem before you solve it.

If the above statement can be applied to a situation, then recursion should be considered an appropriate solution. Literal examples are mainly focussed around either problem solving or search situations, such as breadth/width first search or any divide and conquer algorithm (some of which I’ll be covering in the aforementioned “follow-up articles”). If we boil my definition down into a pseudo-code then it kinda goes like this;

do I know the solution?
Yes: Yay I have the solution! (return)
No: Lets try solving a simpler version of the problem then…(repeat)

You can infer from this that you basically need to know two things when dealing with recursion;

1. How do I know I have reached the solution?
2. How do I simplify the problem?

Or, to put it another way…

1. Stopping Criteria: When should I stop?
2. Simplifying Algorithm: How do I simplify?

In terms of the Stopping Criteria, there are a number of ways that you can identify when to stop simplifying. Maybe you’ve reached your solution, or maybe it is not possible to simplify the problem any more (these two often go hand in hand). The Simplification Algorithm is very bespoke to a given situation, but once you’ve evaluated your problem domain it should be pretty easy to figure out. The following section shows how these two terms work in practice.

Some recursion examples, using the established logical approach

A popular recursion example is the “factorial” problem. Any number “factorial” is basically the number multiplied by each of its iterative successors (down to 1). For example, five factorial is just the result of the following equasion;

5 x 4 x 3 x 2 x 1

If we were avoiding recursion completely and just trying to create a function that would solve this problem using for-loops, it would go something like this;

private static int factorial(int num)
{
  int total = num;
  for(int i = num-1; i > 0; i–)
  {
    total = total * i;
  }
  return total;
}

So, what we’ve ended up with is not nice, readable code and is ridiculously non conventional. The counting expression is a decrementor and the initializer expression involves an equation. It’s perfectly valid code, but it does make your brain work more than it should to figure out what is going on. What I’m about to prove is that solving this problem recursively makes the code more readable.

So as mentioned previously, we know that we need to establish two things: The stopping criteria and the simplifying algorithm. In the case of the factorial problem, these are as follows;

• stopping criteria: The simplest problem is 1 factorial, the answer to which is 1. Therefore, stopping criteria is when we are trying to find the result of 1 factorial.
• Simplification algorithm: Multiply by the number one lower than what I’m currently evaluating.

Therefore, the factorial problem when implemented recursively looks like this;

private static int factorial(int num)
{
  if(num == 1)
    return num;
  else
    return num * factorial(num – 1);
}

Where the “if” part is the stopping criteria, and the “else” part is the simplification algorithm. For a start it’s shorter, but is it more readable? I’d argue that it is. I can clearly see that there are only two possible outcomes to the function: Either I’m at the solution or I’m trying to simplify it.

Okay lets do another one: Imagine you’re doing x to the power of y. So 5 to the power of 4 would be;

5 * 5 * 5 * 5

We won’t bother with the for-loop version this time, let’s just try and figure out how to do this recursively in a logical way. The only two things we need in order to implement recursion, once again, are the stopping criteria and the simplification algorithm. The “simplest solution” in this case would be any number to the power of 1, in which case the result would be the number itself. This is therefore our stopping criteria. In terms of our simplification algorithm, we need to keep multiplying the number by itself until we reach the stopping criteria described previously, so the number of times we multiply is the thing that is getting simpler. Therefore the code goes a little something like this;

private static int power(int num, int toThePowerOf)
{
  if(toThePowerOf == 1)
    return num;
  else
    return num * power(num, toThePowerOf – 1);
}

where once again the “if” part is the stopping criteria, and the “else” part is the simplification algorithm.

In reality, you wouldn’t need to write those kinds of algorithms because if you’re using a half decent framework then they’ll be there for you anyway, but the principles demonstrated here are completely sound when using recursion in practice. For example, a more appropriate use of recursion (which I’m not going to demonstrate here) would be in situations such as tree traversal. In this case, your “stopping criteria” would be when you’ve reached the node you were looking for, and your simplification algorithm would be to search any successor nodes that you haven’t already visited.

Conclusion

Hopefully this has been enough to convince you that recursion is absolutely nothing to be afraid of. It is completely possible to work through its implementation logically and still end up with code that is more readable than the alternative. You should however bear the following in mind;

• only use recursion when it’s appropriate – it IS less readable if applied inappropriately.
• Keep recursive functions short – if a function is getting too big it’s usually an indication that you should do a bit more abstraction first.
• Don’t be freaked out by recursion: It’s just a technique that can be thought about logically and when deployed appropriately will create beautiful, readable code.