Using recursion to sum numbers

Question

I have just been studying the concept of recursion and I thought that I would try a simple example. In the following code, I am attempting to take the numbers: 1, 2, 3, 4, 5, and add them together using recursion. I expected the result to be 15, but my code is returning 16.

What am I doing wrong?

Code:

    static void Main(string[] args)
    {

        Console.WriteLine(Sum(5));
        Console.Read();
    }


    static int Sum(int value)
    {
        if (value > 0)
        {
          return value + Sum(value - 1);
        }
        else
        {
            return 1;
        }
    }

Answer 1

You're returning 1 in the else clause. You should be returning 0:

else
{
    return 0;
}

If the value is not greater than zero, why would you return one in the first place?

Answer 2

Your code executes as follows:

Sum --> 5
  Sum --> 4
    Sum --> 3
      Sum --> 2
        Sum --> 1
          Sum --> 0
          1 <---
        2 <---
      4 <---
    7 <---
  11 <---
16 <---

Check your base case.

Answer 3

static int Sum(int value)
{
    if (value > 0)
    {
        return value + Sum(value - 1);
    }
    else
    {
        return 0; //Change this.
    }
}

Answer 4

That's because, when the value is = 0, you return 1. Then it get's added.

Sum's "else" clause should return 0.

Answer 5

I'm pretty sure the problem is because you want your recursion to terminate when value == 1, and it's currently terminating when value == 0.

Answer 6

Your terminating expression is at issue. When value == 0 (or lower), it should return a 0 rather than 1. For sake of efficiency (which, let's admit it here, obviously isn't a concern, otherwise recursion wouldn't have been used for this task), you should terminate the recursion at value == 1 and return a literal 1 to save one unnecessary level of recursion.

Answer 7

Others already noted the error, and I will elaborate on recursion.

Although C# does not currently perform tail call optimization (although IL has special tail instruction), it's worth mentioning that tail recursion is generally a good thing.

Tail recursion is a special case of recursion in which the last operation of the function, the tail call, is a recursive call. Since the last call is the recursive call there is no need to preserve stack frame of the calling function and the compiler can easily use this information to generate machine instruction such that the stack doesn't grow at all. So it can basically turn recursive function into an iterative one.

Rewriting your code to support tail recursion can be done as follws:

static int Sum(int result, int value)
{
    if(value == 0)
        return result;

    Sum(result + value, value - 1);
}

Answer 8

I always prefer to put the terminating case(s) up front so they're obvious, and I have a violent near-psychopathic hatred of "if cond then return a else return b" constructs. My choice would be (making it clear that it won't work properly for negative numbers):

static unsigned int Sum(unsigned int value) {
    if (value == 0)
        return 0;
    return value + Sum(value - 1);
}

I believe that's far more readable than a morass of braces and control flow.

Answer 9

The others have already answered that question, but when I work with recursion, one of the things I like to do to check that it works is to use check the base case and one additional case. I your case I would test it with 1, which would yield 2. Since this is obviously wrong you might want to check for 0 which is not going to use any recursion and so it should be obvious that the error lies in the base class.

In general recursion is easier to reason about, since you can list the limited number of things you need to check, but it does initially require a leap of faith since your intuition will be wrong. Just test the edge cases and trust the math it will never fail.