1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Is there any particular reason you want to do a recursive implementation instead of an iterative one? This problem is more easily done with an iterative solution. Also, is this the real indentation of your program or did cut/paste do something to it? \$\endgroup\$ – JS1 Aug 17 '15 at 21:37
  • \$\begingroup\$ @JS1 - As for indentation - sorry about that - i pasted it from my vim and it i guess missed out all the spaces for some lines, i don't know why, and for the problem as such, yea i could see iterative solution is way easier, just want to get to the habit of recursive thinking and i'm learning recursions. That is why i'm picking to do this with recursion. \$\endgroup\$ – coderb Aug 17 '15 at 22:15
  • \$\begingroup\$ It could have something to do with tabs. I always replace all tabs with spaces before pasting to stackexchange. \$\endgroup\$ – JS1 Aug 17 '15 at 23:10
1
\$\begingroup\$
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]);
}
\$\endgroup\$
  • \$\begingroup\$ awesome catch! Aiiii macros! :) and nice explanation. \$\endgroup\$ – coderb Aug 21 '15 at 18:09
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.