Understanding Recursion by Understanding Recursion

As I was coming up as a developer, I liked to try my hand at short technical challenges to develop my technical and problem-solving skill.  These may have been implementations of classic computer science problems like Knight’s Tour or Towers of Hanoi or challenges that I had come across during interviews like implementing strrev() or finding a missing number from an array.  I always found these exercises to be both enlightening and fun.

As I gained some experience and found myself conducting interviews, I would go back to these types of questions to determine if a candidate understood various concepts.  One that I used quite frequently was to gauge a developer’s understanding of recursion, which I found to be a decent indicator of being able to understand complicated concepts.

What’s Recursion?

When you first run across recursion, it kind of blows your mind.  A recursive method is a method that calls itself, but how do you define a method that calls a method when that method is itself?  Turns out syntactically, it’s pretty simple.  I used to ask interview candidates to define recursion and then write a quick recursive method on the whiteboard – anything of their choosing.  I recall one implementation quite fondly as it did exactly as I asked:

static void StackOverflow()
{
    StackOverflow();
}

Now, that method didn’t do anything — well, except create a stack overflow, but it certainly met my requirements and no more.

Things get a little more interesting when a recursive method returns a value.  That way, the recursive call return value can be used in a subsequent recursive call (which can be used in a subsequent recursive call).  It’s a way to reduce a problem to a smaller version of the problem coupled with a smaller version of that problem coupled with a smaller version of the smaller version of the problem, etc.

Implementation of N Factorial

A classic example of this problem is a method that computes the factorial of a number.  The factorial of an integer n is defined as the product of n and the integers below it.  For example, 4 factorial – which is written as 4! is 4 * 3 * 2 * 1 or 24.

It may be obvious, but n factorial can then also be written as the product of n and n – 1 factorial: n! = n * (n-1)!  So, if we were to implement a function that computes the factorial of a number n, we may write it like this:

static long Factorial(long number)
{
    return number * Factorial(number - 1);
}

This would be pretty close, but this, like the StackOverflow() method above, will generate a stack overflow.  What’s missing is a termination condition.  We have to stop at some point – when we get to 1:

static long Factorial(long number)
{
    if (number > 1)
    {
        return number * Factorial(number - 1);
    }
    return 1;
}

So, this works out nicely.  If we take 4!, we can see that can be re-written as 4 * 3! and 3! can be re-written as 3 * 2! and 2! can be re-written as 2 * 1! and 1! is 1.  So, we can re-write the whole shebang to 4 * 3 * 2 * 1.

Now, it turns out there is a little hardening that we need to do to this method to make it complete.  For one, the value of 0! is defined as 1, and the value of the factorial of a negative number is undefined.  With that, we can get the following:

static long Factorial(long number)
{
    if (number > 1)
    {
        return number * Factorial(number - 1);
    }
    else if (number >= 0)
    {
        return 1;
    }
    throw new Exception("Factorial is undefined for negative integers");
}

In general, a recursive method has two parts: a base or termination condition and the recursive part.  In the example above the definition of 1! and 0! constitute the base condition.  Those values do not cause the method to recurse.  Other positive values would cause recursion.

Recursion in the Wild

So, now you know how to implement a recursive method, but what else is it good for besides calculating factorials (or Fibonacci or other such things) in the real world?

A good telltale sign of needing recursion is when you think you need a loop but you don’t know how many times you need to iterate.  I came across this at a company I used to work at that had a sales plan that paid commissions based on the depth of that person in the sales organization.  I recall a colleague of mine saying something like needing a loop but not quite a loop.  In that case, a particular sales person’s commission was tied to the commission of the sales person below whose commission was tied to the sales person below, and so on and so forth, up to the sales person that made the sale.  The easy way for us to implement that turned out to be recursion.

Another benefit to knowing how to implement a recursive method?  You can now get through a SharpEcho interview (at least that part)!  If you think you’re ready, drop us a line, we’d love to talk to you!