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

The answer to your question is that, yes, it is possible to reverse an array without iteration. The phrasing of the question itself might be ambiguous, however, the spirit of the question is obvious: a recursive algorithm can be used; and there is no ambiguity at all as to the meaning of recursive in this sense.

If, in an interview situation with a top-flight company, you were asked this question, then the following pseudo-code would be sufficient to demonstrate you truly understood what is meant by recursion:

function reverse(array)      if (length(array) < 2) then         return array      left_half = reverse(array[0 .. (n/2)-1])     right_half = reverse(array[(n/2) .. (n-1)])      return right_half + left_half  end 

For example, if we have an array of 16 elements containing the first 16 letters of the Latin Alphabet, [A]..[P], the above reverse algorithm could be visualised as follows:

                   Original Input  1.                ABCDEFHGIJKLMNOP                   Recurse 2.        ABCDEFGH                IJKLMNOP           Recurse 3.    ABCD        EFGH        IJKL        MNOP       Recurse 4.  AB    CD    EF    GH    IJ    KL    MN    OP     Recurse  5. A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P    Terminate  6.  BA    DC    FE    HG    JI    LK    NM    PO     Reverse 7.    DCBA        HGFE        LKJI        PONM       Reverse 8.        HGFEDCBA                PONMLKJI           Reverse 9.                PONMLKJIHGFEDCBA                   Reverse                    Reversed Output 

Any problem that is solved with a recursive algorithm follows the Divide and Conquer paradigm, namely that:

1. The problem is divided into [two or more] sub-problems where each sub-problem is smaller than, but can be solved in a similar manner to, the original problem (Divide).

2. The problem is divided into [two or more] sub-problems where each sub-problem is independent and can be solved either recursively, or in a straightforward manner if small enough (Conquer).

3. The problem is divided into [two or more] sub-problems where the results of those sub-problems are combined to give the solution for the original problem (Combine).

The pseudo-code above for reversing an array strictly satisfies the above criteria. Thus, it can be considered a recursive algorithm and we can state without any doubt that reversing an array can be done without using iteration.

---

ADDITIONAL BACKGROUND INFORMATION
The difference between Iteration, Recursive Implementations and Recursive Algorithms

It is a common misunderstanding that a recursive implementation means an algorithm is recursive. They are not equivalent. Here is a definitive explanation as to why, including a detailed explanation of the above solution.

---

What are Iteration and Recursion?

Back in 1990, three of the most respected scholars of modern algorithm analysis in the field of computer science, Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest, released their much acclaimed Introduction to Algorithms. In this book, which represented the coming together of over 200 respected texts in their own right, and which for over 20 years has been used as the first and only text for teaching algorithms in most of the top-flight universities around the world, Mssrs. Cormen, Leiserson, and Rivest were explicit about what constitutes Iterating and what constitutes Recursing.

In their analysis and comparison of two classic sorting algorithms, Insertion Sort and Merge Sort, they explain the fundamental properties of iterative and recursive algorithms (sometimes termed incremental algorithms to disambiguate when the classical mathematical notion of iteration is being used in the same context).

Firstly, Insertion Sort is classified as an Iterative algorithm, with its behaviour summarised as follows:

Having sorted the subarray A[1..j-1], we insert the single item A[j] into its proper place, yielding the sorted array A[1..j].

Source: Introduction to Algorithms - Cormen, Leisersen, Rivest, 1990 MIT Press

This statement classifies an Iterative algorithm as one that relies on the result or state of a previous execution ("iteration") of the algorithm, and that such results or state information are then used to solve the problem for the current iteration.

Merge Sort, on the other hand, is classified as a recursive algorithm. A recursive algorithm conforms to a processing paradigm called Divide and Conquer which is a set of three fundamental criteria that differentiate the operation of recursive algorithms from non-recursive algorithms. An algorithm can be considered recursive if, during the processing of a given problem:

1. The problem is divided into [two or more] sub-problems where each sub-problem is smaller than, but can be solved in a similar manner to, the original problem (Divide).

2. The problem is divided into [two or more] sub-problems where each sub-problem can be solved either recursively, or in a straightforward manner if small enough (Conquer).

3. The problem is divided into [two or more] sub-problems where the results of those sub-problems are combined to give the solution for the original problem (Combine).

Reference: Introduction to Algorithms - Cormen, Leisersen, Rivest, 1990 MIT Press

Both Iterative algorithms and Recursive algorithms continue their work until a terminating condition has been reached. The terminating condition in Insertion Sort is that the j'th item has been properly placed in the array A[1..j]. The terminating condition in a Divide and Conquer algorithm is when Criteria 2 of the paradigm "bottoms out", that is, the size of a sub-problem reaches a sufficiently small size that it can be solved without further sub-division.

It's important to note that the Divide and Conquer paradigm requires that sub-problems must be solvable in a similar manner to the original problem to allow recursion. As the original problem is a standalone problem, with no outside dependencies, it follows that the sub-problems must also be solvable as if they were standalone problems with no outside dependencies, particularly on other sub-problems. This means that sub-problems in Divide and Conquer algorithms should be naturally independent.

Conversely, it is equally important to note that input to iterative algorithms is based on previous iterations of the algorithm, and so must be considered and processed in order. This creates dependencies between iterations which prevent the algorithm dividing the problem into sub-problems that can be recursively solved. In Insertion Sort, for example, you cannot divide the items A[1..j] into two sub-sets such that the sorted position in the array of A[j] gets decided before all items A[1..j-1] have been placed, as the real proper position of A[j] may move while any of A[1..j-1] are being themselves placed.

Recursive Algorithms vs. Recursive Implementations

The general misunderstanding of the term recursion stems from the fact there is a common and wrong assumption that a recursive implementation for some task automatically means that the problem has been solved with a recursive algorithm. Recursive algorithms are not the same as recursive implementations and never have been.

A recursive implementation involves a function, or group of functions, that eventually call themselves in order to solve a sub-portion of the overall task in exactly the same manner that the overall task is being solved in. It happens that recursive algorithms (i.e, those that satisfy the Divide and Conquer paradigm), lend themselves well to recursive implementations. However, recursive algorithms can be implemented using just iterative constructs like for(...) and while(...) as all algorithms, including recursive algorithms, end up performing some task repeatedly in order to get a result.

Other contributors to this post have demonstrated perfectly that iterative algorithms can be implemented using a recursive function. In fact, recursive implementations are possible for everything that involves iterating until some terminating condition has been met. Recursive implementations where there is no Divide or Combine steps in the underlying algorithm are equivalent to iterative implementations with a standard terminating condition.

Taking Insertion Sort as an example, we already know (and it has been proven) that Insertion Sort is an iterative algorithm. However, this does not prevent a recursive implementation of Insertion Sort. In fact, a recursive implementation can be created very easily as follows:

function insertionSort(array)      if (length(array) == 1)         return array     end      itemToSort = array[length(array)]     array = insertionSort(array[1 .. (length(array)-1)])      find position of itemToSort in array     insert itemToSort into array      return array  end 

As can be seen, the implementation is recursive. However, Insertion Sort is an iterative algorithm and this we know. So, how do we know that even by using the above recursive implementation that our Insertion Sort algorithm hasn't become recursive? Let us apply the three criteria of the Divide and Conquer paradigm to our algorithm and check.

1. The problem is divided into [two or more] sub-problems where each sub-problem is smaller than, but can be solved in a similar manner to, the original problem.

   YES: Excluding an array of length one, the method for inserting an item A[j] into its proper place in the array is identical to the method used to insert all previous items A[1..j-1] into the array.

2. The problem is divided into [two or more] sub-problems where each sub-problem is independent and can be solved either recursively, or in a straightforward manner if small enough.

   NO: Proper placement of item A[j] is wholly dependent on the array containing A[1..j-1] items and those items being sorted. Therefore, item A[j] (called itemToSort) is not put in the array before the rest of the array is processed.

3. The problem is divided into [two or more] sub-problems where the results of those sub-problems are combined to give the solution for the original problem.

   NO: Being an iterative algorithm, only one item A[j] can be properly placed in any given iteration. The space A[1..j] is not divided into sub-problems where A[1], A[2]...A[j] are all properly placed independently and then all these properly placed elements combined to give the sorted array.

Clearly, our recursive implementation has not made the Insertion Sort algorithm recursive in nature. In fact, the recursion in the implementation in this case is acting as flow control, allowing the iteration to continue until the terminating condition has been met. Therefore, using a recursive implementation did not change our algorithm into a recursive algorithm.

Reversing an Array Without Using an Iterative Algorithm

So now that we understand what makes an algorithm iterative, and what makes one recursive, how is it that we can reverse an array "without using iteration"?

There are two ways to reverse an array. Both methods require you to know the length of the array in advance. The iteration algorithm is favoured for its efficiency and its pseudo-code looks as follows:

function reverse(array)      for each index i = 0 to (length(array) / 2 - 1)         swap array[i] with array[length(array) - i]     next  end 

This is a purely iterative algorithm. Let us examine why we can come to this conclusion by comparing it to the Divide and Conquer paradigm which determines an algorithm's recursiveness.

1. The problem is divided into [two or more] sub-problems where each sub-problem is smaller than, but can be solved in a similar manner to, the original problem.

   YES: Reversal of the array is broken down to its finest granularity, elements, and processing for each element is identical to all other processed elements.

2. The problem is divided into [two or more] sub-problems where each sub-problem is independent and can be solved either recursively, or in a straightforward manner if small enough.

   YES: Reversal of element i in the array is possible without requiring that element (i + 1) (for example) has been reversed or not. Furthermore, reversal of element i in the array does not require the results of other element reversals in order to be able to complete.

3. The problem is divided into [two or more] sub-problems where the results of those sub-problems are combined to give the solution for the original problem.

   NO: Being an iterative algorithm, only one calculation stage is performed at every algorithm step. It does not divide problems into subproblems and there is no merge of the results of two or more sub-problems to get a result.

The above analsys of our first algorithm above confirmed that it does not fit the Divide and Conquer paradigm, and therefore cannot be considered to be a recursive algorithm. However, as both criteria (1) and criteria (2) were satisifed, it is apparent that a recursive algorithm could be possible.

The key lies in the fact that the sub-problems in our iterative solution are of the smallest possible granularity (i.e. elements). By dividing the problem into successively smaller and smaller sub-problems (instead of going for the finest granularity from the start), and then merging the results of the sub-problems, the algorithm can be made recursive.

For example, if we have an array of 16 elements containing the first 16 letters of the Latin Alphabet (A..P), a recursive algorithm would visually look as follows:

                   Original Input  1.                ABCDEFHGIJKLMNOP                   Divide 2.        ABCDEFGH                IJKLMNOP           Divide 3.    ABCD        EFGH        IJKL        MNOP       Divide 4.  AB    CD    EF    GH    IJ    KL    MN    OP     Divide  5. A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P    Terminate  6.  BA    DC    FE    HG    JI    LK    NM    PO     Conquer (Reverse) and Merge 7.    DCBA        HGFE        LKJI        PONM       Conquer (Reverse) and Merge 8.        HGFEDCBA                PONMLKJI           Conquer (Reverse) and Merge 9.                PONMLKJIHGFEDCBA                   Conquer (Reverse) and Merge                    Reversed Output 

From top level, the 16 elements are progressively broken into smaller sub-problem sizes of exactly equal size (levels 1 to 4) until we reach the finest granularity of sub-problem; unit-length arrays in forward order (step 5, individual elements). At this point, our 16 array elements still appear to be in order. However, they are at the same time also reversed as a single element array is also a reversed array in its own right. The results of the single-element arrays are then merged to get eight reversed arrays of length two (step 6), then merged again to get four reversed arrays of length four (step 7), and so on until our original array has been reconstructed in reverse (steps 6 to 9).

The pseudo-code for the recursive algorithm to reverse an array looks as follows:

function reverse(array)      /* check terminating condition. all single elements are also reversed      * arrays of unit length.      */     if (length(array) < 2) then         return array      /* divide problem in two equal sub-problems. we process the sub-problems      * in reverse order so that when combined the array has been reversed.      */     return reverse(array[(n/2) .. (n-1)]) + reverse(array[0 .. ((n/2)-1)])  end 

As you can see, the algorithm breaks the problem into sub-problems until it reaches the finest granularity of sub-problem that gives an instant result. It then reverses the results while they are being merged to give a reversed result array. Although we think that this algorithm is recursive, let us apply the three critera for Divide and Conquer algorithms to confirm.

1. The problem is divided into [two or more] sub-problems where each sub-problem is smaller than, but can be solved in a similar manner to, the original problem.

   YES: Reversing the array at level one can be done using exactly the same algorithm as at level 2, 3, 4, or five.

2. The problem is divided into [two or more] sub-problems where each sub-problem is independent and can be solved either recursively, or in a straightforward manner if small enough.

   YES: Every sub-problem that is not unit length is solved by splitting the problem into two independent sub-arrays and recursively reversing those sub-arrays. Unit length arrays, the smallest arrays possible, are themselves reversed so providing a terminating condition and a guaranteed first set of combine results.

3. The problem is divided into [two or more] sub-problems where the results of those sub-problems are combined to give the solution for the original problem.

   YES: Every problem at levels 6, 7, 8, and 9 are composed only of results from the level immediately above; i.e. of their sub-problems. Reversal of the array at each level results in a reversed result overall.

As can be seen, our recursive algorithm passed the three criteria for the Divide and Conquer paradigm and so can be considered a truly recursive algorithm. Therefore, it is possible to reverse an array without using an iterative algorithm.

It is interesting to note that our original iterative algorithm for array reversal can be implemented using a recursive function. The pseudo code for such an implementation is as follows:

function reverse(array)      if length(array) < 2         return     end      swap array[0] and array[n-1]     reverse(array[1..(n-1)])  end 

This is similar to solutions proposed by other posters. This is a recursive implementation as the defined function eventually calls itself to repeatedly perform the same task over all the elements in the array. However, this does not make the algorithm recursive, as there is no division of the problems into sub-problems, and there is no merging of the results of sub-problems to give the final result. In this case, the recursion is simply being used as a flow-control construct, and algorithmically the overall result can be proved to be performing the same sequence of steps, in exactly the same order, as the original iterative algorithm that was proposed for the solution.

That is the difference between an Iterative Algorithm, a Recursive Algorithm, and a Recursive Implementation.