今天有人问我一个问题，我不相信这是可能的，但我可能是错的，或者我想多了。如何在不使用 C 中的迭代的情况下反转数组？
我的想法是这是不可能的，因为数组可以是任意大小，并且在不使用某种形式的迭代的情况下，没有任何 C 程序可以在考虑到这种支持的情况下表达。
问问题
24127 次
7 回答
86
您的问题的答案是，是的，可以在没有迭代的情况下反转数组。问题本身的措辞可能模棱两可，但问题的精神是显而易见的：可以使用递归算法；在这个意义上，递归的含义一点也不含糊。
如果在与顶级公司的面试中，你被问到这个问题，那么下面的伪代码就足以证明你真正理解了递归的含义：
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 ) 类似的方式解决。
问题分为 [两个或更多] 子问题，其中每个子问题都是独立的，可以递归解决，如果足够小（征服），也可以直接解决。
问题被划分为 [两个或更多] 子问题，其中这些子问题的结果被组合以给出原始问题的解决方案（组合）。
上面用于反转数组的伪代码严格满足上述标准。因此，它可以被认为是一种递归算法，我们可以毫无疑问地声明，可以在不使用迭代的情况下对数组进行反转。
附加背景信息
迭代、递归实现和递归算法之间的区别
递归实现意味着算法是递归的，这是一个常见的误解。它们不是等价的。这是关于原因的明确解释，包括对上述解决方案的详细解释。
什么是迭代和递归？
早在 1990 年，计算机科学领域最受尊敬的三位现代算法分析学者Thomas H. Cormen、Charles E. Leiserson和Ronald L. Rivest发表了他们广受好评的《算法导论》。在这本书中，它代表了 200 多本受人尊敬的文本的汇集，并且 20 多年来一直被用作世界上大多数一流大学教授算法的第一个也是唯一一个文本，Mssrs . Cormen、Leiserson 和 Rivest 明确说明了什么是迭代，什么是递归。
在他们对两种经典排序算法Insertion Sort和Merge Sort的分析和比较中，他们解释了迭代和递归算法的基本属性（有时称为增量算法以消除在相同上下文中使用迭代的经典数学概念时的歧义）。
首先，插入排序被归类为迭代算法，其行为总结如下：
对子数组 A[1.. j -1]进行了排序后，我们将单个项 A[ j ] 插入到适当的位置，产生排序后的数组 A[ 1..j ]。
资料来源：算法简介- Cormen、Leisersen、Rivest，1990 年 MIT 出版社
此语句将迭代算法分类为依赖于算法先前执行（“迭代”）的结果或状态的算法，然后使用此类结果或状态信息来解决当前迭代的问题。
另一方面，归并排序被归类为递归算法。递归算法符合称为分而治之的处理范式，该范式是一组三个基本标准，用于区分递归算法和非递归算法的操作。如果在处理给定问题期间，算法可以被认为是递归的：
问题被划分为 [两个或更多] 子问题，其中每个子问题都小于原始问题，但可以以与原始问题 ( Divide ) 类似的方式解决。
问题分为[两个或更多]子问题，其中每个子问题可以递归解决，或者如果足够小（征服），则可以直接解决。
问题被划分为 [两个或更多] 子问题，其中这些子问题的结果被组合以给出原始问题的解决方案（组合）。
参考：算法简介- Cormen, Leisersen, Rivest, 1990 MIT Press
迭代算法和递归算法都会继续工作，直到达到终止条件。插入排序的终止条件是第j项已正确放置在数组 A[ 1..j ] 中。分治算法的终止条件是范式的标准 2“触底”，即子问题的大小达到足够小的大小，无需进一步细分即可解决。
重要的是要注意分而治之范式要求子问题必须以与原始问题类似的方式可解决，以允许递归。由于原始问题是一个独立问题，没有外部依赖，因此子问题也必须是可解决的，就好像它们是没有外部依赖的独立问题一样，特别是在其他子问题上。这意味着分治算法中的子问题应该是自然独立的。
相反，同样重要的是要注意迭代算法的输入基于算法的先前迭代，因此必须按顺序考虑和处理。这会在迭代之间产生依赖关系，从而阻止算法将问题划分为可以递归解决的子问题。例如，在插入排序中，您不能将项目 A[1.. j ] 分成两个子集，以使 A[ j ] 数组中的排序位置在所有项目 A[1.. j -1之前确定] 已被放置，因为 A[ j ] 的真正正确位置可能会在 A[1.. j -1] 中的任何一个被放置时移动。
递归算法与递归实现
对递归一词的普遍误解源于这样一个事实，即对某些任务的递归实现自动意味着问题已通过递归算法得到解决，这是一个常见且错误的假设。递归算法与递归实现不同，而且从来都不是。
递归实现涉及一个函数或一组函数，它们最终调用自身，以便以与解决整个任务完全相同的方式解决整个任务的子部分。递归算法（即，那些满足分而治之范式的），很适合递归实现。但是，递归算法可以仅使用迭代构造来实现for(...)，while(...)因为所有算法，包括递归算法，最终都会重复执行某些任务以获得结果。
这篇文章的其他贡献者已经完美地证明了迭代算法可以使用递归函数来实现。事实上，递归实现对于涉及迭代直到满足某个终止条件的所有事情都是可能的。在底层算法中没有 Divide 或 Combine 步骤的递归实现等效于具有标准终止条件的迭代实现。
以插入排序为例，我们已经知道（并且已经证明）插入排序是一种迭代算法。但是，这并不妨碍插入排序的递归实现。实际上，可以很容易地创建递归实现，如下所示：
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
可以看出，实现是递归的。但是，插入排序是一种迭代算法，我们知道这一点。那么，我们怎么知道即使使用上面的递归实现，我们的插入排序算法也没有变成递归的呢？让我们将分而治之范式的三个标准应用于我们的算法和检查。
问题被分成[两个或更多]子问题，其中每个子问题小于原始问题，但可以以与原始问题类似的方式解决。
YES：不包括长度为 1 的数组，将项 A[ j ] 插入数组中适当位置的方法与将所有先前项 A[ 1..j -1] 插入数组的方法相同。
问题被划分为[两个或更多]子问题，其中每个子问题都是独立的，可以递归解决，如果足够小，也可以直接解决。
否：项目 A[ j ]的正确放置完全取决于包含 A[1.. j -1] 项目的数组以及正在排序的项目。因此，在处理数组的其余部分之前，不会将项 A[ j ]（称为itemToSort）放入数组中。
问题被分成[两个或更多]子问题，其中这些子问题的结果被组合起来以给出原始问题的解决方案。
NO：作为一种迭代算法，只有一个项目 A[ j ] 可以正确放置在任何给定的迭代中。空间 A[1.. j ] 没有被划分为子问题，其中 A[1]、A[2]...A[ j ] 都被适当地独立放置，然后所有这些适当放置的元素组合起来给出排序大批。
显然，我们的递归实现并没有使插入排序算法本质上是递归的。实际上，在这种情况下，实现中的递归起到了流控制的作用，允许迭代继续进行，直到满足终止条件。因此，使用递归实现并没有将我们的算法更改为递归算法。
在不使用迭代算法的情况下反转数组
因此，既然我们了解了是什么使算法迭代，又是什么使一个递归，那么我们如何“不使用迭代”来反转一个数组呢？
有两种方法可以反转数组。这两种方法都要求您提前知道数组的长度。迭代算法因其效率而受到青睐，其伪代码如下所示：
function reverse(array)
for each index i = 0 to (length(array) / 2 - 1)
swap array[i] with array[length(array) - i]
next
end
这是一个纯粹的迭代算法。让我们通过将其与决定算法递归性的分而治之范式进行比较来检验为什么我们可以得出这个结论。
问题被分成[两个或更多]子问题，其中每个子问题小于原始问题，但可以以与原始问题类似的方式解决。
YES：数组的反转被分解为最细的粒度、元素，并且每个元素的处理与所有其他处理的元素相同。
问题被划分为[两个或更多]子问题，其中每个子问题都是独立的，可以递归解决，如果足够小，也可以直接解决。
YES ：数组中元素i的反转是可能的，而不需要元素(i + 1)（例如）是否反转。此外，数组中元素i的反转不需要其他元素反转的结果即可完成。
问题被分成[两个或更多]子问题，其中这些子问题的结果被组合起来以给出原始问题的解决方案。
NO：作为一种迭代算法，每个算法步骤只执行一个计算阶段。它不会将问题划分为子问题，也不会合并两个或多个子问题的结果以获得结果。
我们上面第一个算法的上述分析证实它不符合分治范式，因此不能被认为是递归算法。然而，由于标准 (1) 和标准 (2) 都得到满足，显然递归算法是可能的。
关键在于我们迭代解决方案中的子问题具有最小可能的粒度（即元素）。通过将问题划分为越来越小的子问题（而不是从一开始就追求最细粒度），然后合并子问题的结果，可以使算法递归。
例如，如果我们有一个包含 16 个元素的数组，其中包含拉丁字母 (A..P) 的前 16 个字母，则递归算法在视觉上看起来如下所示：
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
从顶层开始，16 个元素逐渐分解为大小完全相同的较小子问题（级别 1 到 4），直到我们达到子问题的最细粒度；正向排列的单位长度数组（第 5 步，单个元素）。此时，我们的 16 个数组元素看起来仍然是有序的。但是，它们同时也是反转的，因为单个元素数组本身也是反转数组。然后将单元素数组的结果合并得到八个长度为 2 的反向数组（步骤 6），然后再次合并得到四个长度为 4 的反向数组（步骤 7），依此类推，直到我们的原始数组被重构反过来（步骤 6 到 9）。
递归算法反转数组的伪代码如下所示：
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
正如您所看到的，该算法将问题分解为子问题，直到它达到子问题的最细粒度，从而提供即时结果。然后在合并结果时反转结果以提供反转的结果数组。虽然我们认为这个算法是递归的，但让我们应用分治算法的三个标准来确认。
问题被分成[两个或更多]子问题，其中每个子问题小于原始问题，但可以以与原始问题类似的方式解决。
YES：可以使用与级别 2、3、4 或 5 完全相同的算法在级别 1 反转数组。
问题被划分为[两个或更多]子问题，其中每个子问题都是独立的，可以递归解决，如果足够小，也可以直接解决。
是：每个不是单位长度的子问题都可以通过将问题分成两个独立的子数组并递归地反转这些子数组来解决。单位长度数组（可能的最小数组）本身是反转的，因此提供了终止条件和保证的第一组组合结果。
问题被分成[两个或更多]子问题，其中这些子问题的结果被组合起来以给出原始问题的解决方案。
是：第 6、7、8 和 9 级的每个问题仅由上一级的结果组成；即他们的子问题。在每个级别上反转阵列会导致总体上反转的结果。
可以看出，我们的递归算法通过了分治范式的三个标准，因此可以被认为是真正的递归算法。因此，可以在不使用迭代算法的情况下反转数组。
有趣的是，我们最初的数组反转迭代算法可以使用递归函数来实现。这种实现的伪代码如下：
function reverse(array)
if length(array) < 2
return
end
swap array[0] and array[n-1]
reverse(array[1..(n-1)])
end
这类似于其他海报提出的解决方案。这是一个递归实现，因为定义的函数最终会调用自身以对数组中的所有元素重复执行相同的任务。然而，这并没有使算法递归，因为没有将问题划分为子问题，也没有合并子问题的结果来给出最终结果。在这种情况下，递归只是被用作流控制结构，并且在算法上可以证明整体结果以完全相同的顺序执行相同的步骤序列，与为解决方案。
这就是迭代算法、递归算法和递归实现之间的区别。
于 2012-07-06T10:36:47.800 回答
23
正如人们在评论中所说，这取决于迭代的定义。
案例 1. 迭代作为一种编程风格，不同于递归
如果将递归（简单地）作为迭代的替代方案，那么 Kalai 提出的递归解决方案就是正确的答案。
案例 2. 迭代作为下限线性时间
如果将迭代视为“检查每个元素”，那么问题就变成了数组反转是否需要线性时间还是可以在亚线性时间内完成。
为了表明没有用于数组反转的次线性算法，请考虑具有n 个元素的数组。假设存在不需要读取每个元素的反转算法A。然后存在a[i]一些算法从不读取i的元素0..n-1，但仍然能够正确反转数组。（编辑：我们必须排除奇数长度数组的中间元素——请参阅此范围内的以下评论——请参阅下面的评论——但这不会影响算法在渐近情况下是线性的还是次线性的。）
由于算法从不读取元素a[i]，我们可以更改它的值。说我们这样做。然后，该算法根本没有读取过这个值，它将产生与我们改变它的值之前相同的反转答案。但是这个答案对于 的新值是不正确的a[i]。因此，不存在至少不读取每个输入数组元素（保存一个）的正确反转算法。因此，数组反转的下限为 O(n)，因此需要迭代（根据此场景的工作定义）。
（请注意，此证明仅适用于数组反转，并没有扩展到真正具有亚线性实现的算法，例如二分查找和元素查找。）
案例 3. 作为循环结构的迭代
如果将迭代视为“循环直到满足条件”，那么这将转换为具有条件跳转的机器代码，已知需要一些严重的编译器优化（利用分支预测等）在这种情况下，有人问是否存在做一些“没有迭代”的方法可能会考虑循环展开（到直线代码）。在这种情况下，您原则上可以编写直线（无循环）C 代码。但这种技术并不通用；仅当您事先知道数组的大小时，它才有效。（很抱歉将这个或多或少轻率的情况添加到答案中，但我这样做是为了完整性，因为我听说过以这种方式使用的术语“迭代”，而循环展开是一个重要的编译器优化。）
于 2012-07-04T05:06:34.497 回答
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)
于 2012-07-04T04:47:16.860 回答
1
实现一个递归函数来反转一个排序的数组。即，给定数组 [1, 2, 3, 4, 5]，您的过程应该返回 [5, 4, 3, 2, 1]。
于 2013-07-29T14:47:39.547 回答
0
这是一个在 javascript 函数中使用递归的巧妙解决方案。它不需要数组本身以外的任何参数。
/* 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;
}
}
如下调用它；
reverse([1,2,3,4]);
请注意，如果您不使用嵌套函数 copyChop 进行数组切片，您最终会得到一个数组作为最终结果中的第一个元素。不太清楚为什么会这样
于 2013-06-28T10:13:02.197 回答
0
#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]);
}
}
于 2014-03-13T02:35:11.813 回答
0
一种解决方案可能是：
#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;
}
于 2022-02-13T19:53:02.383 回答