今天有人向我提出一个问题,我不相信这是可能的,但我可能是错的,或者我在想它.如何在不使用C中的迭代的情况下反转数组？
我的想法是,这是不可能的,因为数组可以是任何大小的事实,没有使用某种形式的迭代,没有C程序可以用这种支持表达.
aps*_*012 82
您的问题的答案是,是的,可以在没有迭代的情况下反转数组.问题本身的措辞可能含糊不清,但问题的精神是显而易见的:可以使用递归算法; 在这个意义上,对于递归的含义一点也没有含糊之处.
如果在与顶级公司的面谈情况中,您被问到这个问题,那么下面的伪代码就足以证明您真正理解了递归的含义:
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
例如,如果我们有一个包含拉丁字母的前16个字母的16个元素的数组,[A] .. [P],上面的反向算法可以显示如下:
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
使用递归算法解决的任何问题都遵循Divide and Conquer范式,即:
该问题分为[两个或更多]子问题,其中每个子问题小于,但可以以与原始问题(Divide)类似的方式解决.
问题分为[两个或更多]子问题,其中每个子问题是独立的,并且可以递归地解决,或者如果足够小(Conquer)则以简单的方式解决.
该问题分为[两个或更多]子问题,其中这些子问题的结果被组合以给出原始问题的解决方案(组合).
上面用于反转数组的伪代码严格满足上述标准.因此,它可以被认为是一种递归算法,我们可以毫无疑问地说明,可以在不使用迭代的情况下完成对数组的反转.
附加背景信息
迭代,递归实现和递归算法之间的区别
一种常见的误解是递归实现意味着算法是递归的.他们并不等同.以下是对原因的明确解释,包括对上述解决方案的详细说明.
什么是迭代和递归？
早在1990年,三位最受尊敬的计算机科学领域的现代算法分析学者Thomas H. Cormen,Charles E. Leiserson和Ronald L. Rivest就发布了备受好评的算法导论.在这本书中,它代表了200多个受人尊敬的文本的汇集,20多年来,它被用作世界上大多数顶级大学教学算法的第一个也是唯一的文本,Mssrs .Cormen,Leiserson和Rivest明确指出迭代的构成以及Recursing的构成.
在他们对两种经典排序算法(插入排序和合并排序)的分析和比较中,他们解释了迭代和递归算法的基本属性(有时称为增量算法,以便在同一上下文中使用经典的迭代数学概念时消除歧义).
首先,Insertion Sort被归类为迭代算法,其行为总结如下:
在对子阵列A [1 .. j -1] 进行排序后,我们将单个项目A [ j ]插入到其适当的位置,从而产生排序的数组A [1 .. j ].
资料来源:算法导论 - Cormen,Leisersen,Rivest,1990麻省理工学院出版社
该语句将迭代算法分类为依赖于算法的先前执行("迭代")的结果或状态的迭代算法,并且然后使用这样的结果或状态信息来解决当前迭代的问题.
另一方面,Merge Sort被归类为递归算法.递归算法符合称为Divide and Conquer的处理范例,这是一组三个基本标准,用于区分递归算法和非递归算法的操作.如果在处理给定问题期间,算法可以被认为是递归的:
该问题分为[两个或更多]子问题,其中每个子问题小于,但可以以与原始问题(Divide)类似的方式解决.
问题分为[两个或更多]子问题,其中每个子问题可以递归地解决,或者如果足够小(Conquer)则以简单的方式解决.
该问题分为[两个或更多]子问题,其中这些子问题的结果被组合以给出原始问题的解决方案(组合).
参考:算法导论 - Cormen,Leisersen,Rivest,1990麻省理工学院出版社
迭代算法和递归算法都会继续工作,直到达到终止条件.插入排序中的终止条件是第j项已正确放置在数组A [1 .. j ]中.分而治之算法中的终止条件是当范式的标准2"触底"时,即,子问题的大小达到足够小的尺寸,使得它可以在没有进一步细分的情况下被解决.
值得注意的是,Divide and Conquer范例要求子问题必须能够以与原始问题类似的方式解决才能允许递归.由于最初的问题是一个独立的问题,没有外部依赖性,因此子问题也必须是可解的,就像它们是没有外部依赖性的独立问题一样,特别是在其他子问题上.这意味着Divide and Conquer算法中的子问题应该是自然独立的.
相反,同样重要的是要注意迭代算法的输入是基于算法的先前迭代,因此必须按顺序考虑和处理.这会在迭代之间产生依赖关系,从而阻止算法将问题划分为可以递归求解的子问题.例如,在插入排序中,您不能将项目A [1 .. j ]分成两个子集,以便在所有项目A [1 .. j -1 之前确定A [ j ] 数组中的排序位置已被放置,因为A [ j ] 的真正适当位置可能会移动,而A [1 .. j -1]中的任何一个本身都被放置.
递归算法与递归实现
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.
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.
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.
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.
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.
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.
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.
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.
Ray*_*oal 23
正如人们在评论中所说,它取决于迭代的定义.
如果将递归(简单地)作为迭代的替代,那么Kalai提出的递归解决方案就是正确的答案.
如果将迭代视为"检查每个元素",则问题变为阵列反转是需要线性时间还是可以在次线性时间内完成.
为了表明没有用于阵列反转的次线性算法,请考虑具有n个元素的数组.假设存在用于反转的算法A,其不需要读取每个元素.然后存在一个元件a[i]对于一些i在0..n-1该算法从不读取,但仍然能够正确地扭转该阵列.(编辑:我们必须排除奇数长度数组的中间元素 - 请参阅下面的注释 - 请参阅下面的注释 - 但这不会影响算法在渐近情况下是线性的还是次线性的.)
由于算法永远不会读取元素,a[i]我们可以更改其值.说我们这样做.然后,从未读过这个值的算法将产生与我们改变其值之前相同的逆转答案.但这个答案对于新的价值来说是不正确的a[i].因此,不存在至少读取每个输入数组元素(保存一个)的正确反转算法.因此,阵列反转具有O(n)的下限,因此需要迭代(根据该场景的工作定义).
(请注意,此证明仅适用于阵列反转,并未扩展到真正具有子线性实现的算法,如二进制搜索和元素查找.)
如果迭代被视为"循环直到满足条件",则转换为具有条件跳转的机器代码,已知需要一些严格的编译器优化(利用分支预测等).在这种情况下,有人询问是否存在做"无迭代"的方法可能会考虑循环展开(直线代码).在这种情况下,您原则上可以编写直线(无环路)C代码.但这种技术并不普遍; 只有事先知道数组的大小才有效.(很抱歉将这个或多或少的轻率情况添加到答案中,但我这样做是为了完整性,因为我听说过以这种方式使用的术语"迭代",循环展开是一个重要的编译器优化.)
Kal*_*avi 14
使用递归函数.
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);
}
只需将上述方法称为reverse(array,0,lengthofarray-1)