Q:

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

I encountered the following question in an interview. 
Complete this function to return a reversed array without modifying the function signature or the original array. Note that static data types should not be used here at all.
Assume the arrayLength is a power of 2. i.e 2^n. -> I think this is the trick here.
int* reverse(int *array, int arrayLength){

}

Please help.
Note that I could not really think of a solution to the problem. The interviewer hinted at using 2^n for the puspose, but i could not really think of the solution.

A:

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

