writing C function using only recursion

Question

I want to find out if the sum of even numbers in the array is equal to the sum of odd numbers, using only recursion and without any additional functions, except recursion and without any static variables.

If the sum of odd numbers is equal to the sum of even numbers, the function returns 1, else it returns 0. All the numbers in the array are non negative.

The function signature should look like this:

function(unsigned int a[], int n)

Until now I have written the following:

function(unsigned int a[], int n)
{ 
    if(n==0) return 0;
    return (a[0]%2)?((a[0]+function(a+1,n-1)):(-a[0]+function(a+1,n-1));
}

This function returns the total sum required but not the answer to the question (which is 1 if yes and 0 if no).

Yes this is a part of an assignment but I cannot solve it without additional functions that are not allowed.

Seems impossible given the signature. Might be possible with a different signature. — Eugene Sh.
– Eugene Sh., Commented Jun 13, 2016 at 21:27
I suppose, you are trying to implement wrong alorithm.... consider using static (or global) variables for storing sum(s) — VolAnd
– VolAnd, Commented Jun 13, 2016 at 21:30
Darn.. Just written a nice answer assuming we are talking about odd and even indices.. — Eugene Sh.
– Eugene Sh., Commented Jun 13, 2016 at 21:51

jxh · Accepted Answer · 2016-06-21 16:03:30Z

9

If we assume no overflow in the calculations:

int function (unsigned int a[], int n) {
    if (n >= 0) return !function(a, -n-1);
    if (++n == 0) return 0;
    return function(a+1, n) + ((a[0] % 2) ? -a[0] : a[0]);
}

On first call into the function, the n is nonnegative, and reflects the size of the array. We recursively call the function and logically negate the result, and arithmetically negate n+1. The off by one negation allows -1 to represent 0
On subsequent calls, the sum of evens are positively accumulated, and odds are negatively accumulated. The negative n is incremented until it reaches 0. The result of the recursive calls on the negative n is 0 if the sums are equal, and non-zero otherwise.
On return to the outermost call, the logical negation flips it so that 1 is returned if the sums are equal and 0 otherwise.

I'll leave it as an exercise to appropriately deal with overflow.

edited Jun 21, 2016 at 16:03

answered Jun 13, 2016 at 21:41

jxh

70.9k8 gold badges116 silver badges204 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Picodev Over a year ago

nice, short and elegant !

evgniy tayarov Over a year ago

i just forgot to mention one thing which is: if n==0 return 1; because an empty array is considered as correct because the sum of evens equals to the odds, and both are 0 on this case.

jxh Over a year ago

@evgniytayarov Fixed.

Community · Accepted Answer · 2017-05-23 12:31:49Z

3

A mod to @jxh nifty answer.

A typical complaint against recursion function is in using up the stack. With N elements, having N levels of recursion may exhaust the recursion limit.

The following instead uses log2(N) levels of recursion by dividing the array in half per each call.

int function(const int a[], int n) {
  if (n > 0) return !function(a, -n);
  if (n == 0) return 0;
  if (n == -1) return (a[0] % 2) ? -a[0] : a[0];
  int half = n/2;
  int left = function(a, half);
  int right = function(&a[-half], -(-n - -half));
  return left + right;
}

edited May 23, 2017 at 12:31

CommunityBot

11 silver badge

answered Jun 14, 2016 at 5:08

chux

158k17 gold badges160 silver badges311 bronze badges

2 Comments

jxh Over a year ago

Nice (upvoted). I would probably change the last 4 lines to return function(a, n/2) + function(a-n/2, n-n/2);

chux Over a year ago

@jxh True, your simplification is correct. This answer posted in steps as it was easy to mess up the math considering that sneaky - sign your nifty trick employs.

jxh · Accepted Answer · 2016-06-21 21:39:38Z

This was my solution which is much more complex than yours and in a bad and unneeded way.

int balanced(unsigned int a[], int n)
{
    if (n <= 2)
    {
        int odd = 0, even = 0;
        if (a[0]%2 == 0) even += a[0];
        else odd += a[0];
        if (a[1]%2 == 0 && n == 2) even += a[1];
        else if (n == 2) odd += a[1];
        return (odd == even);
    }

    if (a[0]%2 == 0 && a[1]%2 == 0)
    {
        a[1] += a[0];
        return balanced(a+1, n-1);
    }
    if (a[0]%2 == 0 && a[2]%2 == 0)
    {
        a[2] += a[0];
        return balanced(a+1, n-1);
    }
    if (a[1]%2 == 0 && a[2]%2 == 0)
    {
        a[2] += a[1];
        a[1] = a[0];
        return balanced(a+1, n-1);
    }
    if (a[0]%2 == 0)
    {
        if (a[0] >= a[1]+a[2])
        {
            a[0] -= (a[1]+a[2]);
            a[2] = a[0];
            return balanced(a+2,n-2);
        }
        else
        {
            a[1] = a[1]+a[2]-a[0]-1;
            a[2] = 1;
            return balanced(a+1,n-1);
        }
    }
    if (a[1]%2 == 0)
    {
        if (a[1] >= a[0]+a[2])
        {
            a[1] -= (a[0]+a[2]);
            a[2] = a[1];
            return balanced(a+2,n-2);
        }
        else
        {
            a[0] = a[0]+a[2]-a[1]-1;
            a[2] = 1;
            a[1] = a[0];
            return balanced(a+1,n-1);
        }
    }
    if (a[2]%2 == 0)
    {
        if (a[2] >= a[1]+a[0])
        {
            a[2] -= (a[1]+a[0]);
            return balanced(a+2,n-2);
        }
        else
        {
            a[1] = a[1]+a[0]-a[2]-1;
            a[0] = 1;
            a[2] = a[0];
            return balanced(a+1,n-1);
        }
    }
    else
    {
        a[2] = a[0]+a[1]+a[2];
        return balanced(a+2,n-2);
    }
}

Collectives™ on Stack Overflow

writing C function using only recursion

3 Answers 3

3 Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related