Reverse an integer array of length 2^n recursively and return a new array without modifying the original

How about this:

int* reverse(int *array, int arrayLength){
  if (arrayLength==1) {
    int* out=(int*)malloc(sizeof(int));
    out[0] = array[0];
    return out;
  }
  int* left = reverse(array+arrayLength/2, arrayLength-arrayLength/2);
  int* right = reverse(array,arrayLength/2);
  int* out = (int*)realloc(left, sizeof(int)*arrayLength);
  memcpy(out+arrayLength/2, right, sizeof(int)*(arrayLength/2));
  free(right);
  return out;
}

Agree with OP the the hint is "2^n". As with many recursive functions: divide and conquer.

This routine first deals with errant paramters and the simple lengths. Next, divide the length in half and reverse each half. Form the result by concatenating the reversed left and right sub-arrays. First, right, then left.

Usual clean-up follows

#include <string.h>
#include <stdlib.h>


int* reverse(int *array, int arrayLength) {
  // Check parameters
  if (array == NULL || arrayLength < 0) {
    ; // TBD HandleBadParameters();
  }

  // Allocate space for result, not much to do if length <= 1
  int *y = malloc(arrayLength * sizeof *y);
  if (y == NULL) {
    ; // TBD HandleOOM();
  }
  if (arrayLength <= 1) {
    memcpy(y, array, arrayLength * sizeof *y);
    return y;
  }

  // Find reverse of the two halves
  int halflength = arrayLength / 2;
  int *left = reverse(array, halflength);
  int *right = reverse(&array[halflength], halflength);

  // Append them to the result - in reverse order
  memcpy(y, right, halflength * sizeof *y);
  memcpy(&y[halflength], left, halflength * sizeof *y);

  // Clean-up and return
  free(right);
  free(left);
  return y;
}

int* reverse(int *array, int arrayLength){
    if(arrayLength == 0) return array;
    int* ret = (int*)malloc(arrayLength*sizeof(int));
    for(int i=0;i<arrayLength;i++) ret[i] = array[arrayLength-1-i];
    return reverse(ret, 0); // technically recursive
}

Here it is (and works):

int *reverse(int *array, int arrayLength)
{
    if (arrayLength > 1) {
        int i, n = arrayLength >> 1;
        int *m = calloc(n, sizeof(int));

        memcpy(m, array, n*sizeof(int));
        memcpy(array, array + n, n*sizeof(int));
        memcpy(array + n, m, n*sizeof(int));
        free(m);
        reverse(array, n); 
        reverse(array+n, n); 
    } /* for */
    return array;
} /* reverse */

it can be done without temporary storage, but you have to iterate a little.

int *reverse(int *a, int al) 
{
    if (al > 1) {
        int i, a1 = al >> 1;

        for (i = 0; i < a1; i++) {
            int temp = a[i];
            a[i] = a[i + a1];
            a[i + a1] = temp;
        } /* for */
        reverse(a, a1);
        reverse(a+a1, a1);
    } /* for */
    return a;
} /* reverse */

but, it would be nicer just to exchange from the boundaries to the middle and do it completely iterative.

int *reverse(int *array, int arrayLength)
{
    int a, b;
    for (a = 0, b = arrayLength-1; a < b; a++, b--) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    } /* for */
    return array;
} /* reverse */

And just for the ones who asked for a non selfmodifying array, this all-inefficient form:

int *reverse(int *array, int arrayLength)
{
    int *a1, *a2;
    int *res;

    if (arrayLength > 1) {
        int l = arrayLength >> 1;
        a1 = reverse(array, l);
        a2 = reverse(array + l, l);
        res = calloc(arrayLength, sizeof(int));
        memcpy(res, a2, l*sizeof(int));
        memcpy(res+l, a1, l*sizeof(int));
        free(a1);
        free(a2);
    } else {
        /* we return always memory alloc'd with malloc() so we have to do this. */
        res = malloc(sizeof(int));
        *res = array[0];
    } /* if */

    return res;

} /* reverse */

Well, here's one sneaky way, and it doesn't care what length the array is. Note: I'm assuming you can't introduce a new function, it has to be done all within the existing function

if the length is postive, it allocates memory and makes a copy, then calls reverse again with a negative length and the copy, then if the function is called with a negative length, it reverses the first and last inplace, then recursively calls by moving to the next in the array and shrinks the length till there is nothing left to reverse and then the recursive function unwinds

int* reverse(int *array, int arrayLength){
        int* result;
        if(arrayLength > 0)
        {
            result =(int*) malloc((sizeof(int)*arrayLength));
            memcpy(result, array, sizeof(int)*arrayLength);
            reverse(result, -arrayLength);
            return result;
        }
        else if(arrayLength < -1)
        {
            int end = (-arrayLength)-1;
            int temp = array[end];
            array[end] = array[0];
            array[0] = temp;
            return reverse(array+1, arrayLength+2);
        }   
        return array;
    }

Considering that arrayLength is always a power of 2. we will apply the function to the two parts of the array then concat them in the reverse way. Finaly if the array has only one element, we simply return other array with the same element.

int* reverse(int *array, int arrayLength){
    int * newArray = NULL;
    if(arrayLength == 1){
        newArray = (int *)malloc(sizeof(int));
        *newArray = array[0];
    } else if(arrayLength == 2){
        newArray = (int *)malloc(2 * sizeof(int));
        newArray[0] = array[1];
        newArray[1] = array[0];
    } else {
        // apply to first half
        int * first = reverse(array, arrayLength / 2);
        // apply to second half
        int * second = reverse(array + arrayLength / 2, arrayLength / 2);
        // allocate space
        newArray = (int *) malloc(arrayLength * sizeof(int));
        // copy parts in reverse way
        memcpy(newArray, second, arrayLength / 2 * sizeof(int));
        memcpy(newArray + arrayLength / 2, first, arrayLength / 2 * sizeof(int));
        // free allocated space for parts
        free(first);
        free(second);
    }
    return newArray;
}

I'll give it a shot.

Knowing that the array is of length 2^n means that it can be safely halved. We call the function recursively on each half until length is 2. At this point we swap the two integers. Think { 2,1,4,3,6,5,8,7 }. When we come back from that, each half is then merged opposite of where it came from ( { 4,3,2,1,8,7,6,5} ). Rinse and repeat.

#include <stdio.h>
#include <stdlib.h>

int * reverse( int* arr, int length )
{

  if ( length == 1 )
  {
    int *result = malloc( sizeof( arr[0] ) );
    result[0] = arr[0];
    return result;
  }

  int * result = 0;

  if ( length == 2 )
  {
    result = malloc( sizeof( arr[0] ) * 2 );
    result[0] = arr[1];
    result[1] = arr[0];
  }
  else
  {
    int half_length = length / 2;

    // named correctly
    int * right = reverse( arr, half_length );
    int * left  = reverse( arr + half_length, half_length );

    result = malloc( sizeof( arr[0] ) * length );

    for ( int i = 0; i < half_length; ++i )
    {
      result[i] = left[i];
      result[ i + half_length ] = right[i];
    }

    free( right );
    free( left );
  }

  return result;

}

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

  int *reversed = reverse( arr, length );

  for ( int i = 0; i < length; ++i )
  {
    printf( "%d %d\n", arr[i], reversed[i] );
  }

  free( reversed );
  return 0;
}

for all integer arrays with more than 2 elements. The basic idea is to swap elements from both ends untill the number of elements remaining is 1.

int* reverse_array(int* array, int arrayLength) {

if(arrayLength <2)
{
    return NULL;
}
else
{
     int *array1 = NULL;
     int *array2 = NULL;
     array1 = malloc(arrayLength*sizeof(int));
     memcpy(array1,array,arrayLength*sizeof(int));

     /*swap the start and end*/
     swap(array1,(array1+arrayLength-1));

      /* swap the next pair */
     array2 = reverse_array(array1+1,arrayLength-2);
     memcpy(array1+1,array2,(arrayLength-2)*sizeof(int));

     if(array2!= NULL)
     {
        free(array2);
     }
     return array1;
}

}