Using recursion to add odd numbers

Question

Hi Friends,

I am trying to write a method to calculate the sum of the odd numbers in all the numbers less than the given number. so eg. CalcOdd(7) would return 5 + 3 + 1 = 9. CalcOdd (10) would return 9 + 7 + 5 + 3 + 1 = 25 etc

The method needs to take in a number, subtract 1, then recursively work backwards adding all odd numbers until it reaches 0. This is what I have so far.

    private static int CalcOdd(int n)
    {            

        if (n <= 1)
            return 1;
        else
            if (n % 2 == 0)
                n--;

        return n + CalcOdd(n - 2);
    }

It doesn't work so well, it includes the number passed in in the addition which is not what I want. Can anyone suggest a better way of doing this ? I would also loke to be able to port the answer to work for even numbers and add the option to include the original passed in number in the answer.

Many thanks

Answer 1

Why would you use recursion here? Just loop; or better, figure out the math to do it in a simple equation...

The fact is that C# doesn't make for excellent deep recursion for things like maths; the tail-call isn't really there at the moment.

Loop approach:

private static int CalcOdd(int n)
{
    int sum = 0, i = 1;
    while (i < n)
    {
        sum += i;
        i += 2;
    }
    return sum;
}

Answer 2

Why use recursion?

private Int32 CalcOdd(Int32 value)
{
    Int32 r = 0;
    {
     while (value >= 1)
     {
      value--;
      if (value % 2 != 0)
      {
       r += value;
      }
     }    
    }
    return r;
}

Answer 3

the sum of odd numbers less than a given number is a perfect square.

get the whole part of (n/2) to get the number of odd number less than itself.

square that and voila!

private static int CalcSumOdd(int n)
{            
    int i;
    int.tryParse(n / 2, out i);
    return i*i;
}

for even numbers its:

int i = n/2;
return i*(i+1);

correction. The above "even number sum" includes the original number "n". ie fn(12) = 42 = 2 + 4 + 6 + 8 + 10 + 12

if you want to exclude it, you should either unilaterally exclude it, or remove it with logic based on a passed in parameter.

Answer 4

Use a helper function. CalcOdd consists of testing n to see if it is even or odd; if it is even, return helper(n); if it is odd, return helper(n-2).

The helper function must handle three cases: 1) n is less than 1; in this case return 0. 2) n is even, in this case return helper(n-1). 3) n is odd, in this case return n+helper(n-1).

Answer 5

You could do this with recursion as you say, but if you wish to do it quicker, then I can tell you that the sum of the n first odd numbers is equal to n*n.

private static int CalcOdd(int n) {
    if (n<=1)
     return 0;

    if (n%2 == 1)
     n--;

    int k = n/2;

    return k*k;
}

The reason this works is:

Every even number is of the form 2k, and the odd number before it is 2k-1.

Because 2*1-1 = 1, there are k odd numbers below 2k.

If n is odd, we don't want to include it, so we simply go down to the even number below it and we automatically have what we want.

Edited to fix broken code.

Answer 6

int CalcOdd(int n)
{            
    n -= 1;

    if (n <= 0)
     return 0; 

    if (n % 2 == 0)
     n--;

    return n + CalcOdd(n);
}

This function is also recursive, and it has parameters which makes you able to decide wether to do even or odd number and wether you want to include the first number or not. If you are confused as to how it works, remember that bools also can be seen as 1 (true) and 0 (false)

int Calc(int n, bool even = false, bool includeFirst = false)
{           
    n -= !includeFirst;

    if (n <= 0)
        return 0; 

    if (n % 2 == even)
        n--;

    return n + Calc(n - includeFirst, even);
}

Answer 7

public static int CalcOdd(int n) {
    // Find the highest even number. (Either n, or n-1.)
    // Divide that by 2, and the answer should be the square of that number.
    n = (n & 0x3FFFFFFE) >> 1;
    return (int)Math.Pow(n, 2);
}

Answer 8

Here is a correction,

int CalcOdd(int n)
{ 
        n--; // <----

        if (n <= 1)
            return 0; // <----
        else
            if (n % 2 == 0)
                n--;

        return n + CalcOdd(n); // <----
}

Answer 9

Simple loop verion.

    private static int CalcOdd(int number)
    {
        if (number < 2)
            return 1;
        int i = (number & 1) == 1 ? number - 2 : number - 1, result = 0;
        for (; i > 0; i -= 2)
            result += i;
        return result;
    }

Answer 10

Since you want the option of including or excluding the first answer (and, keeping your "recursion" constraint in mind):

int calcOdd(int n, bool includeN)
{
    if( !includeN )
        return calcOdd(n-1, true);
    if(n<=1)
        return 1;
    else
        if(n%2 == 0)
            n--;
    return n+calcOdd(n-1, true);
}

The includeFirst, if passed as true, will include n in the calculations. Otherwise, the next layer down will start "including N".

Granted, as others have said, this is a horribly inefficient use of recursion, but... If you like recursion, try Haskell. It's a language built almost entirely on the concept.

Answer 11

Håkon, I have ported your code to c# in VS 2008 as follows

        static int Calc(int n, bool bEven, bool bIncludeFirst)
    {
        int iEven = Bool2Int(bEven);
        int iIncludeFirst = Bool2Int(bIncludeFirst);

        n -= 1 - iIncludeFirst;

        if (n <= 0)
            return 0;

        if (n % 2 == iEven)
            n--;

        return n + Calc(n - iIncludeFirst, bEven, bIncludeFirst);
    }


    private static int Bool2Int(bool b)
    {
        return b ? 1 : 0;
    }

It seems to be working. Now is there anything I can do to optomise ? i.e. I dont want to have to parse those bools to ints every time etc ?

Answer 12

i'm new here but this seems like a silly recursion exercise, given it can be done with a simple equation:

int sum(n,isEven,notFirst) {
    int c=1; //skip the else
    if (isEven) c=2;
    if (notFirst) n-=2;
    return ((n+c)*((n+c)/2))/2; }

classic discrete math sum series.. sum from 1 to 100 (odds and evens) is ((100+1)*(100/2))=5050

edit: in my code here, if you're calculating the sum of odds with n being even, or vice versa, it doesn't work, but i'm not going to put the work into that (and slop the code) right now. i'll assume your code will take care of that by the time it hits the function.. for example 7/2 isn't an int (obviously)

Answer 13

I'd isolate the 'make it odd' part from the 'sum every other descending number' part: (forgive the Python)

def sumEveryTwoRecursive(n):
    if n <= 0:
        return 0
    return n + sumEveryTwoRecursive(n - 2)

def calcOdd(n):
    return sumEveryTwoRecursive(n - (2 if n % 2 else 1))

Answer 14

Just because there isn't one here yet, I've decided to use the LINQ hammer on this nail...

(borrowed from Nick D and Jason's pair programmed answer here)

void Main()
{
    GetIterator(7, true, false).Sum().Dump();
    // Returns 9

    GetIterator(10, true, false).Sum().Dump();
    // Returns 25
}

public IEnumerable<int> GetIterator(int n, bool isOdd, bool includeOriginal)
{   
    if (includeOriginal)
        n++;

    if (isOdd)
        return GetIterator(n, 1);
    else
        return GetIterator(n, 0);
}

public IEnumerable<int> GetIterator(int n, int odd)
{
    n--;

    if (n < 0)
        yield break;

    if (n % 2 == odd)
        yield return n;

    foreach (int i in GetIterator(n, odd))
        yield return i;
}