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:
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).
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).
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:
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).
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).
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.
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.
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.
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.
