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.

Answer 1

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.

Answer 2

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;
}