Finding difference between adjacent integers in an array - recursive Implementation

Question

I'm trying to do a recursive implementation of the problem mentioned below.

The code works, and takes care of a corner case with only 1 element in array (in which case I should return 0 - (element[]). Could there be improvements to this solution (like say not having to pass 4 arguments or anything like similar).

Also, I don't like that count variable because its used only for 1 purpose (finding that corner case of only 1 element in original array). How can I bypass that?

(This is not a homework problem; I'm trying to learn recursion.)

Examples

input Array: {1, 2, 3, 4, 5} Difference output: {1, 1, 1, 1}

input Array: {2} Difference output: {-2}

input Array: {2, 5, 1} Difference output: {3, -4}

void differenceSequence(int array[], int n, int count, int resultArray[]) {


if (n == 0 && count == 0) {
    /* Only 1 element in array */
    resultArray[n] = -1 * array[n];
    return;
}
if(n == 0) {
    /* second base case where size will be 0, and array recursion should end */
    return;
}
resultArray[n-1] = array[n] - array[n-1];
differenceSequence(array, n-1, ++count, resultArray);
}

int main() {

int *array = (int*) malloc (sizeof(int) * ARRAY_SIZE);
int *resultArray= (int*) malloc (sizeof(int) * ARRAY_SIZE-1);
int i = 0, size = ARRAY_SIZE;

// array = (int[ARRAY_SIZE]){5, 4, 3, -1, 0};
array = (int[ARRAY_SIZE]){1};

differenceSequence(array, ARRAY_SIZE-1, 0, resultArray);

/* Print Arrays */
printf("Original Array \n");
for (i = 0; i < size; i++) {
    printf("%d \t", array[i]);
}
printf("\n");

/* Check for result array where there is only 1 element in original
 * array
 */
if(ARRAY_SIZE == 1) {
    size = ARRAY_SIZE;
} else {
    size = ARRAY_SIZE - 1;
}

printf("Difference Array \n");
for (i = 0; i < size; i++) {
    printf("%d \t", resultArray[i]);
}
printf("\n");


return 0;
}

Answer 1

int *resultArray= (int*) malloc (sizeof(int) * ARRAY_SIZE-1);

is wrong, it needs to be (sizeof(int) * (ARRAY_SIZE-1));

Then you can also solve the problem by going the whole recursion first, which means the first code that is actually executed is the one for n == 0, instead for n == n. This then allows you to handle the corner case as regular case of n, instead of special case of count.

void differenceSequence(int array[], int n, int resultArray[])
{
  if(n == 0) return;
  else differenceSequence(array, n-1, resultArray);    

  if(n == 1) resultArray[n-1] = -1 * array[n-1];
  else resultArray[n-2] = array[n-1] - array[n-2];
}

This leads to the following lines being executed:

n = 1
resultArray[0] = -1 * array[0];

---

n = 2
 n = 1
  resultArray[0] = -1 * array[0];
   n = 2
    resultArray[0] = array[1] - array[0];

---

n = 3
  n = 1
   resultArray[0] = -1 * array[0];
    n = 2
      resultArray[0] = array[1] - array[0];
      n = 3
        resultArray[1] = array[2] - array[1];

---

Then your function returns void, yet there is one information you actually want/need - the size of the result array. You can either return it or, due to the change of the execution order, you could also pass it upwards:

void differenceSequence(int array[], int n, int resultArray[], int* resultn)
{
  ...

  if(n == 1)
  {
    resultArray[n-1] = - 1 * array[n-1];
    *resultn = n;
  }
  else
  {
    resultArray[n-2] = array[n-1] - array[n-2];
    *resultn = n - 1;
  }
}

And so you can use it like this:

differenceSequence(array, ARRAY_SIZE, resultArray, &j);
printf("Difference Array\n");
for (i = 0; i < j; i++) {
    printf("%d \t", resultArray[i]);
}

Answer 2

In situations like this, it is much simpler to handle the corner case outside the recursive call:

    differenceSequence(int array[], int size, int resultArray[])
    {
        if (size == 0) {
            do_corner_case();
            return;
        }
        differenceSequenceRecursive(array, size, resultArray);
    }

and the helper differenceSequenceRecursive function only deals with regular case.