Reverse an array without using iteration

Question

A question was asked to me today and I do not believe it is possible, but I could be wrong or am over thinking it. How can you reverse an array without using iteration in C?

My thought is that it's impossible because of the fact that the array can be any size and that no C program can be expressed with that kind of support in mind without using some form of iteration.

Answer 1

As people have said in the comments, it depends on the definition of iteration.

Case 1. Iteration as a programming style, different from recursion

If one takes recursion (simply) as an alternative to iteration, then the recursive solution presented by Kalai is the right answer.

Case 2. Iteration as lower bound linear time

If one takes iteration as "examining each element," then the question becomes one of whether array reversal requires linear time or can be done in sublinear time.

To show there is no sublinear algorithm for array reversal, consider an array with n elements. Assume an algorithm A exists for reversal which does not need to read each element. Then there exists an element a[i] for some i in 0..n-1 that the algorithm never reads, yet is still able to correctly reverse the array. (EDIT: We must exclude the middle element of an odd-length array -- see the comments below from this range -- see the comments below -- but this does not impact whether the algorithm is linear or sublinear in the asymptotic case.)

Since the algorithm never reads element a[i] we can change its value. Say we do this. Then the algorithm, having never read this value at all, will produce the same answer for reversal as it did before we changed its value. But this answer will not be correct for the new value of a[i]. Hence a correct reversal algorithm which does not at least read every input array element (save one) does not exist. Hence array reversal has a lower bound of O(n) and thus requires iteration (according to the working definition for this scenario).

(Note that this proof is only for array reversal and does not extend to algorithms that truly have sublinear implementations, like binary search and element lookup.)

Case 3. Iteration as a looping construct

If iteration is taken as "looping until a condition is met" then this translates into machine code with conditional jumps, known to require some serious compiler optimization (taking advantage of branch prediction, etc.) In this case, someone asking if there is a way to do something "without iteration" may have in mind loop unrolling (to straight line code). In this case you can in principle write straight-line (loop-free) C code. But this technique is not general; it only works if you know the size of the array beforehand. (Sorry to add this more-or-less flippant case to the answer, but I did so for completeness and because I have heard the term "iteration" used in this way, and loop unrolling is an important compiler optimization.)

Answer 2

Use recursive function.

void reverse(int a[],int start,int end)
{
     int temp;
     temp = a[start];
     a[start] = a[end];
     a[end] = temp;


    if(start==end ||start==end-1)
       return;
    reverse(a, start+1, end-1);
}

Just call the above method as reverse(array,0,lengthofarray-1)

Answer 3

Implement a recursive function to reverse a sorted array. Ie, given the array [ 1, 2, 3, 4, 5] your procedure should return [5, 4, 3, 2, 1].

Answer 4

Here's a neat solution using recursion in a javascript function. It does not require any parameters other than the array itself.

/* Use recursion to reverse an array */
function reverse(a){
    if(a.length==undefined || a.length<2){
        return a;
    }
    b=[];
    b.push(reverse(copyChop(a)));
    b.push(a[0]);
    return b;
    /* Return a copy of an array minus the first element */
    function copyChop(a){ 
        b=a.slice(1); 
        return b;
    }
}

Call it as follows;

reverse([1,2,3,4]);

Note that if you don't use the nested function copyChop to do the array slicing you end up with an array as the first element in your final result. Not quite sure why this should be so

Answer 5

   #include<stdio.h>


   void rev(int *a,int i,int n)
  {

if(i<n/2)
{
    int temp = a[i];
    a[i]=a[n-i-1];
    a[n-i-1]=temp;
    rev(a,++i,n);
 }
}
int main()
    {
    int array[] = {3,2,4,5,6,7,8};
   int len = (sizeof(array)/sizeof(int));
   rev(array,0,len);    
   for(int i=0;i<len;i++)
   {
    printf("\n array[%d]->%d",i,array[i]);
  }
}

Answer 6

One solution could be:

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

void swap(int v[], int v_start, int v_middle, int v_end) {
    int *aux = calloc(v_middle - v_start, sizeof(int));
    
    int k = 0;
    for(int i = v_start; i <= v_middle; i++) {
        aux[k] = v[i];
        k = k + 1;
    }

    k = v_start;
    for(int i = v_middle + 1; i <= v_end; i++) {
        v[k] = v[i];
        k = k + 1;
    }

    for(int i = 0; i <= v_middle - v_start; i++) {
        v[k] = aux[i];
        k = k + 1;
    }
}

void divide(int v[], int v_start, int v_end) {
    if(v_start < v_end) {
        int v_middle = (v_start + v_start)/2;
        divide(v, v_start, v_middle);
        divide(v, v_middle + 1, v_end);
        swap(v, v_start, v_middle, v_end);
    }
}

int main() {
    int v[10] = {4, 20, 12, 100, 50, 9}, n = 6;
    
    printf("Array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", v[i]);
    }
    printf("\n\n");

    divide(v, 0, n - 1);

    printf("Reversed: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", v[i]);
    }

    return 0;
}