Reversing int array using recursion in C

Question

I have learnt C language at school but I'm not good at it... And when I was trying to implement this algorithm using C language:

ReverseArray(int A[], int i, int j) {
   Input: Array A, nonnegative integer indices i and j
   Output: The reversal of the elements in A starting at index i and ending at j
   if i < j then
      swap A[i] and A[j]
      ReverseArray(A, i+1, j-1)
}

I managed to code this:

int *reverseArray(int A[], int i, int j) {
   int *R = NULL;
   if(i < j) {
      int temp = A[j];
      A[j] = A[i];
      A[i] = temp;
      R = reverseArray(A, i+1, j-1);
      return R;
   } else {
      return R;
   }
}

But when I tried to print the original and reversed array in the main:

int main(void) {
   int A[] = {1, 3, 5, 6, 8, 3, 4, 2};

   int *r = reverseArray(A, 0, 7);

   //This prints out the reversed array, when I intended to print the original
   for (size_t i = 0; i < 8; i++) {
      printf("%d ", A[i]);
   }
   printf("\n");

   /* This was intended to print the reversed array but doesn't work
   for (size_t i = 0; i < 8; i++) {
      printf("%d ", r[i]);
   }
   */

   return 0;
}

Could anyone please explain why the commented out for loop doesn't work? And why the first for loop prints out the reversed array... Is there any other way to get the result of reverseArray() without using *r? I tried to malloc *r just in case that was the problem, but it still didn't work.

Thank you.

Oh you're right! But then, what should I be returning instead? That's where you have to stop the recursion right? (when i == j....or larger) — Ceria
– Ceria, Commented Jul 3, 2015 at 12:12
Make it void reverseArray(). You don't need to return anything. The data is changed directly. — pmg
– pmg, Commented Jul 3, 2015 at 12:13
Thank you! Returning A fixed it :D And yes, changing it to void also helped! — Ceria
– Ceria, Commented Jul 3, 2015 at 12:25

CiaPan · Accepted Answer · 2015-07-03 12:22:35Z

2

Just don't return anything. You make a reversion in place, so the resulting array is the same as the array to be reversed, and the caller knows it already.

answered Jul 3, 2015 at 12:22

CiaPan

9,5802 gold badges23 silver badges38 bronze badges

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

Comments

jarmod · Accepted Answer · 2015-07-03 12:25:00Z

2

You need to print the contents of A before you call reverseArray, not after. The reason is that you are reversing the bytes in place so the array A itself is changed by calling reverseArray.

answered Jul 3, 2015 at 12:25

jarmod

79.8k18 gold badges132 silver badges137 bronze badges

1 Comment

Ceria Over a year ago

haha that's true! I can't believe I got confused about that, thank you.

Eric Tsui · Accepted Answer · 2015-07-03 12:46:59Z

1

A try from your code base and the problem description

If allowed to rewrite the Array in place, then it will work

#include<stdio.h>

void reverseArray(int A[], int i, int j) {
   //int *R = NULL;
   if(i < j) {
      int temp = A[j];
      A[j] = A[i];
      A[i] = temp;
      reverseArray(A, i+1, j-1);
   }
}

int main(void) {
   int A[] = {1, 3, 5, 6, 8, 3, 4, 2};

   //This prints out original array
   for (size_t i = 0; i < 8; i++) {
      printf("%d ", A[i]);
   }
   printf("\n");

   reverseArray(A, 0, 7);

   // print the reversed array
   for (size_t i = 0; i < 8; i++) {
      printf("%d ", A[i]);
   }

   return 0;
}

It will Output:

1 3 5 6 8 3 4 2
2 4 3 8 6 5 3 1

edited Jul 3, 2015 at 12:46

answered Jul 3, 2015 at 12:37

Eric Tsui

1,93213 silver badges23 bronze badges

Comments

eroween · Accepted Answer · 2015-07-03 12:41:39Z

0

R is always assigned to NULL, and A is not a pointer, then you are editing the real data of the array.

if you want to reverse and create a new array, you must do something like that :

int *reverseArray(int array[], int arraySize) {
    int *reversedArray = malloc(sizeof(int) * arraySize);

    for ( int i = 0 ; i < arraySize ; ++i ) {
        reversedArray[i] = array[arraySize - i - 1];
    }
    return reversedArray;
}

You can also do it in recursive way :

int   *reverseArray(int inputArray[], int arrayLength ) {

    int   *_reverseArray (int inputArray[], int arrayLength, int *outputArray, int actual) {

            if (outputArray == NULL) {
                outputArray = malloc(sizeof(int) * arrayLength);
            }
            if (actual < arrayLength) {
                outputArray[actual] = inputArray[arrayLength - actual - 1];
                return _reverseArray(inputArray, arrayLength, outputArray, ++actual);
            }
            return outputArray;

    }
    return _reverseArray(inputArray, arrayLength, NULL, 0);
}

If you want to edit the original array :

void    reverseArray(int array[], int arraySize)
{
    for ( int i = 0 ; i < arraySize / 2 ; ++i ) {
        array[i] ^= array[arraySize - i - 1];
        array[arraySize - i - 1] ^= array[i];
        array[i] ^= array[arraySize - i - 1];
  }
}

edited Jul 3, 2015 at 12:41

answered Jul 3, 2015 at 12:10

eroween

17311 bronze badges

3 Comments

Ceria Over a year ago

Oh that makes sense, that I am using the original A as a parameter... But if that's the case, what should I do with the else loop? If I don't write anything, there's a compiler error... Also do I still need int *r = reverseArray() in the main then? Even if I'm not going to use r afterwards?

Quentin Over a year ago

@Ceria if you're reversing the array in-place, there is no need to return anything. Just declare the function as returning void.

Spikatrix Over a year ago

array[arraySize - i] accesses array[arraySize] (invalid memory location) in the first iteration.

Collectives™ on Stack Overflow

Reversing int array using recursion in C

4 Answers 4

Comments

1 Comment

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

1 Comment

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related