颠倒数组而不使用迭代
我今天问了一个问题，我不相信这是可能的，但我可能是错的，或者是在想这个问题。 如何在C中不使用迭代来反转数组？
我的想法是，这是不可能的，因为这个数组可以是任意大小的，并且没有使用某种forms的迭代就不能用这种支持来expressionC程序。
你的问题的答案是， 是的，有可能颠倒一个数组没有迭代 。 问题本身的含义可能是模棱两可的，但问题的精神是显而易见的：可以使用recursionalgorithm; 从这个意义上说， recursion的含义是毫不含糊的。
如果在一家顶级公司的采访中，你被问到了这个问题，那么下面的伪代码就足以certificate你真正理解了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 例如，如果我们有一个包含拉丁字母前16个字母的16个元素的数组，[A] … [P]，则上述反向algorithm可以如下显示：
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. ABCDEFGHIJKLMNOP 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
任何用recursionalgorithm解决的问题都遵循分而治之的范式，即：
-
问题被分成[两个或更多个]子问题，其中每个子问题小于原始问题（ Divide ），但可以以类似的方式解决。
-
问题分为[两个或两个以上]子问题，其中每个子问题是独立的，可以recursion解决，或者如果足够小（ 征服 ）， 则以直接的方式解决。
-
问题分为[两个或多个]子问题，这些子问题的结果组合起来，给出原始问题的解决scheme（ 组合 ）。
上述用于反转数组的伪代码严格满足上述标准。 因此，它可以被认为是一个recursionalgorithm，我们可以毫无疑问地表明，颠倒数组可以在不使用迭代的情况下完成。
附加的背景信息
迭代，recursion实现和recursionalgorithm的区别
recursion实现意味着一个algorithm是recursion的，这是一个常见的误解。 他们不相同。 这里是一个明确的解释，为什么，包括上述解决scheme的详细解释。
什么是迭代和recursion？
早在1990年，计算机科学领域中最受尊敬的现代algorithm分析学者Thomas H. Cormen ， Charles E. Leiserson和Ronald L. Rivest就发表了他们备受赞誉的“algorithm导论” 。 在这本书中，这本书代表了超过200本备受推崇的教科书，20多年来被世界上绝大多数顶尖大学用作教学algorithm的第一本也是唯一一本教科书，Mssrs 。 Cormen，Leiserson和Rivest明确了什么是循环 ，什么是循环 。
在分析和比较两种经典的sortingalgorithm， 插入sorting和合并sorting时 ，他们解释了迭代algorithm和recursionalgorithm的基本属性（有时被称为增量algorithm，以消除迭代的经典math概念在相同的上下文中被使用的情况）。
首先，插入sorting被分类为迭代algorithm，其行为总结如下：
对子数组A [1， j -1]进行sorting后，将单个项A [ j ]插入到适当的位置，产生sorting后的数组A [1， j ]。
来源： algorithm介绍 – Cormen，Leisersen，Rivest，1990 MIT出版社
该陈述将迭代algorithm归类为依赖于algorithm的先前执行（“迭代”）的结果或状态，并且然后使用这样的结果或状态信息来解决当前迭代的问题。
另一方面，合并sorting被归类为recursionalgorithm。 recursionalgorithm符合被称为“ 分而治之”（Divide and Conquer）的处理范例，该处理范式是一组三个基本标准，其将recursionalgorithm的操作与非recursionalgorithm的操作区分开来。 如果在给定问题的处理过程中，algorithm可以被认为是recursion的：
-
问题被分成[两个或更多个]子问题，其中每个子问题小于原始问题（ Divide ），但可以以类似的方式解决。
-
这个问题被分成[两个或更多个]子问题，其中每个子问题可以recursion地解决，或者如果足够小（ 征服 ）， 则以直接的方式解决。
-
问题分为[两个或多个]子问题，这些子问题的结果组合起来，给出原始问题的解决scheme（ 组合 ）。
参考： algorithm介绍 – Cormen，Leisersen，Rivest，1990麻省理工学院出版社
迭代algorithm和recursionalgorithm都继续工作，直到达到终止条件 。 插入sorting中的终止条件是第j个项目已被正确放置在数组A [ 1..j ]中。 “分而治之”algorithm中的终止条件是当范例的标准2“落底”时，即子问题的大小达到足够小以至于不需要进一步细分就可以解决的问题。
需要注意的是，“分而治之”的范式要求子问题必须以与原始问题类似的方式解决，以允许recursion。 由于原始问题是一个独立的问题，没有外部依赖关系，因此子问题也必须是可以解决的，就好像它们是没有外部依赖关系的独立问题， 尤其是在其他子问题上 。 这意味着“分而治之”algorithm中的子问题应该是自然独立的 。
相反，同样重要的是要注意，迭代algorithm的input是基于algorithm的先前迭代，因此必须按顺序考虑和处理。 这会在迭代之间产生依赖关系，从而阻止algorithm将问题分解为可recursion解决的子问题。 例如，在“插入sorting”中，不能将项目A [ 1..j ]分成两个子集，以便在A [ j ]的数组中sorting的位置在所有项A [1 .. j -1 ]被放置，因为A [ j ]的实际正确位置可以移动而A [1， j -1]中的任何一个正被放置。
recursionalgorithm与recursion实现
对recursion这个术语的普遍误解源于这样一个事实，即有一个常见的错误的假设，即某个任务的recursion实现自动意味着该问题已经用recursionalgorithm解决了。 recursionalgorithm与recursion实现不一样，从来没有。
recursion实现包含一个函数或一组函数，最终调用它们自己以完全解决总体任务的一个子部分来解决整个任务的子部分。发生recursionalgorithm （即，那些满足“分而治之”范式的人）很好地适应recursion实现。 然而，recursionalgorithm可以使用像for(...)和while(...)这样的迭代结构来实现，因为包括recursionalgorithm在内的所有algorithm都会重复执行一些任务以获得结果。
这篇文章的其他贡献者已经很好地展示了迭代algorithm可以使用recursion函数来实现。 事实上，recursion实现对于涉及迭代的所有事情都是可能的，直到满足一些终止条件。 在底层algorithm中没有Divide或Combine步骤的recursion实现相当于具有标准终止条件的迭代实现。
以插入sorting为例，我们已经知道（并且已经certificate）插入sorting是一种迭代algorithm。 但是，这并不妨碍Insertion Sort的recursion实现 。 实际上，recursion实现可以很容易地创build，如下所示：
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
可以看出，这个实现是recursion的。 然而，插入sorting是一个迭代algorithm，这是我们知道的。 那么，我们怎么知道，即使通过使用上面的recursion实现，我们的插入sortingalgorithm还没有成为recursion？ 让我们把分而治之范式的三个标准应用到我们的algorithm和检查。
-
问题分为两个或两个以上的子问题，其中每个子问题都小于原问题，但可以用类似的方式解决。
是 ：排除长度为1的数组，将项目A [ j ]插入到数组中适当位置的方法与将所有先前项目A [1 … j -1]插入到数组中的方法相同。
-
问题分为[两个或两个以上]子问题，其中每个子问题是独立的，可以recursion解决，或者在足够小的情况下以直接的方式解决。
否 ：正确放置项目A [ j ]完全取决于包含A [ 1..j -1]项目的数组以及正在sorting的项目。 因此，在处理数组的其余部分之前，项A [ j ]（称为itemToSort ）未放入数组中。
-
问题分为[两个或两个以上]子问题，这些子问题的结果组合起来解决原始问题。
NO ：作为迭代algorithm，在任何给定的迭代中只能有一个项目A [ j ]被正确放置。 空间A [ 1..j ]不分为A [1]，A [2] … A [ j ]都被正确地独立放置的子问题，然后所有这些正确放置的元素组合在一起，arrays。
显然，我们的recursion实现并没有使插入sortingalgorithm在本质上recursion。 事实上，在这种情况下，实现中的recursion是作为stream量控制 ，允许迭代继续，直到达到终止条件。 因此，使用recursion实现并不会将我们的algorithm转换为recursionalgorithm。
在不使用迭代algorithm的情况下反转数组
所以现在我们明白了什么使algorithm迭代，什么使得recursion，我们如何能够“不使用迭代”来颠倒数组？
有两种方法可以反转数组。 这两种方法都要求您事先知道数组的长度。 迭代algorithm是有利于其效率和伪代码如下所示：
function reverse(array) for each index i = 0 to (length(array) / 2 - 1) swap array[i] with array[length(array) - i] next end
这是一个纯粹的迭代algorithm。 让我们来看看为什么我们可以通过将它与决定algorithmrecursion性的分而治之（Divide and Conquer）范式进行比较来得出这个结论。
-
问题分为两个或两个以上的子问题，其中每个子问题都小于原问题，但可以用类似的方式解决。
是 ：数组的反转被细分为最细粒度的元素，每个元素的处理与所有其他处理的元素相同。
-
问题分为[两个或两个以上]子问题，其中每个子问题是独立的，可以recursion解决，或者在足够小的情况下以直接的方式解决。
是 ：数组中元素i的反转是可能的，而不需要元素（i + 1） （例如）已被反转或不反转。 此外，为了能够完成，数组中元素i的反转不需要其他元素反转的结果。
-
问题分为[两个或两个以上]子问题，这些子问题的结果组合起来解决原始问题。
否 ：作为迭代algorithm，每个algorithm步骤只执行一个计算阶段。 它不会将问题分解为子问题，也不会将两个或多个子问题的结果合并来得到结果。
上面的第一个algorithm的上面的analsys证实它不符合Divide and Conquer范式，因此不能被认为是一个recursionalgorithm。 然而，由于标准（1）和标准（2）都满足，显然recursionalgorithm是可能的。
关键在于我们的迭代解决scheme中的子问题具有尽可能小的粒度（即元素）。 通过将问题分成越来越小的子问题（而不是从一开始就以最好的粒度进行），然后合并子问题的结果，可以使algorithmrecursion。
例如，如果我们有一个包含拉丁字母（A..P）的前16个字母的16个元素的数组，则recursionalgorithm在视觉上将如下所示：
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. ABCDEFGHIJKLMNOP 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个arrays元素依然显得有序。 但是，它们同时也是相反的，因为单个元素数组本身也是一个倒序数组。 然后合并单元素数组的结果，得到8个长度为2的反转数组（步骤6），然后再次合并以得到四个长度为4的反转数组（步骤7），依此类推，直到我们的原始数组被重构反向（步骤6到9）。
用于recursion数组的逆代码的伪代码如下所示：
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
正如你所看到的，该algorithm将问题分解为子问题，直到它达到最佳的子问题粒度，从而给出即时结果。 然后在合并它们的同时反转结果以得到相反的结果数组。 虽然我们认为这个algorithm是recursion的，但是让我们使用三个分而治之algorithm来确认。
-
问题分为两个或两个以上的子问题，其中每个子问题都小于原问题，但可以用类似的方式解决。
是的 ：在第一级反转数组可以使用完全相同的algorithm在第2,3,4或5级。
-
问题分为[两个或两个以上]子问题，其中每个子问题是独立的，可以recursion解决，或者在足够小的情况下以直接的方式解决。
是 ：每一个非单位长度的子问题都是通过将问题分解成两个独立的子数组并recursion地反转这些子数组来解决的。 单位长度数组（可能的最小数组）本身是反向的，因此提供了终止条件和保证的第一组组合结果。
-
问题分为[两个或两个以上]子问题，这些子问题的结果组合起来解决原始问题。
是 ：第6,7,8和9级的每一个问题都只包含上一级的结果。 即其子问题。 在每个级别的数组的反转导致总体上相反的结果。
可以看出，我们的recursionalgorithm通过了“分而治之”范式的三个标准，因此可以被认为是一个真正的recursionalgorithm。 因此， 可以在不使用迭代algorithm的情况下反转数组。
值得注意的是，我们的原始数组反转迭代algorithm可以使用recursion函数来实现 。 这种实现的伪代码如下所示：
function reverse(array) if length(array) < 2 return end swap array[0] and array[n-1] reverse(array[1..(n-1)]) end
这与其他海报提出的解决scheme相似。 这是一个recursion实现，因为定义的函数最终会调用它自己来重复执行数组中所有元素的相同任务。 但是，这并没有使algorithmrecursion，因为没有将问题分解为子问题，并且没有将子问题的结果合并来给出最终结果。 在这种情况下，recursion被简单地用作stream量控制结构，并且在algorithm上，可以certificate整体结果是按照与提出的原始迭代algorithm完全相同的顺序执行相同的步骤序列解。
这就是迭代algorithm ， recursionalgorithm和recursion实现之间的区别。
正如人们在评论中所说，这取决于迭代的定义。
案例1.迭代作为编程风格，与recursion不同
如果将recursion（简单地）作为迭代的替代方法 ，那么Kalai提出的recursion解决scheme是正确的答案。
情况2.迭代为下限线性时间
如果将迭代看作是“检查每个元素”，那么问题就变成arrays反转需要线性时间还是可以在次线性时间完成。
为了显示数组倒置没有次线性algorithm，考虑一个有n个元素的数组。 假设存在反转的algorithmA ，其不需要读取每个元素。 然后在0..n-1中存在一个元素a[i] ，这个algorithm从不读取，但仍然能够正确地反转数组。 （ 编辑 ：我们必须排除奇数长度数组的中间元素 – 请参阅下面的注释 – 请参阅下面的注释 – 但这并不影响algorithm在渐近情况下是线性的还是次线性的。
由于algorithm从不读取元素a[i]我们可以改变它的值。 说我们这样做。 那么algorithm，从来没有读过这个值，将会产生相同的反转答案，就像我们改变它的值之前一样。 但是这个答案对于a[i]的新值是不正确的。 因此，不存在至less读取每个input数组元素（保存一个）的正确的反转algorithm。 因此arrays反转有一个O（n）的下界，因此需要迭代（根据这个场景的工作定义）。
（请注意，这个certificate只适用于数组逆转，并没有扩展到真正具有次线性实现的algorithm，如二进制search和元素查找。）
情况3.迭代作为循环构造
如果迭代被视为“循环直到满足条件”，那么这将转换成带有条件跳转的机器码，已知需要一些严重的编译器优化（利用分支预测等）。在这种情况下，有人询问是否存在可以考虑循环展开 （以直线代码）。 在这种情况下，您可以原则上编写直线（无循环）C代码。 但是这种技术不是一般的; 它只适用于事先知道数组大小的情况。 （对不起，在这个答案中增加了这个或多或less的错误情况，但是我这样做是为了完整性，因为我已经听说过使用这种方式的“迭代”，循环展开是一个重要的编译器优化。
使用recursion函数。
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); }
只需将上述方法调用为反向（array，0，lengthofarray-1）
实现一个recursion函数来反转已sorting的数组。 也就是说，给定数组[1,2,3,4,5]，你的过程应该返回[5,4,3,2,1]。
这是一个整洁的解决scheme，在javascript函数中使用recursion。 它不需要除数组本身以外的任何参数。
/* 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来执行数组切片，则最终结果中的数组将作为第一个元素。 不太清楚为什么会这样
#include<stdio.h> void rev(int *a,int i,int n) { if(i<n/2) { int temp = a[i]; a[i]=a[ni-1]; a[ni-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]); } }
