algorithm

反转数组而不使用迭代

发布于 2021-01-31 15:56:23

今天有人问了我一个问题，我不认为这是可能的，但我可能错了，或者正在思考。如何在不使用C语言进行迭代的情况下反转数组？

我的想法是不可能的，因为数组可以是任意大小，并且如果不使用某种形式的迭代，就不能在考虑这种支持的情况下表达C程序。

关注者

被浏览

1 个回答

面试哥 2021-01-31

为面试而生，有面试问题，就找面试哥。
您的问题的答案是， 是的，无需迭代即可反转数组 。问题本身的措词可能不明确，但是问题的实质很明显：可以使用递归算法；从这个意义上说，递归
的含义完全没有歧义。

如果在与一家顶级公司的采访中，有人问到了这个问题，那么下面的伪代码足以证明您 真正了解 了递归的含义：
```
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个字母[A] .. [P]的16个元素组成的数组，则上述反向算法可以如下所示：
```
                   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
```
用递归算法解决的任何问题都遵循 分而治之 范式，即：
1. 该问题分为[两个或多个]子问题，其中每个子问题都小于，但可以通过与原始问题（ Divide ）类似的方式解决。
2. 该问题分为[两个或多个]子问题，其中每个子问题都是独立的，可以递归地解决，或者如果足够小则可以直接解决（ Conquer ）。
3. 该问题分为[两个或多个]子问题，这些子问题的结果被合并以给出原始问题的解决方案（ Combine ）。
上面用于反转数组的伪代码严格满足上述条件。因此，它可以被认为是一种递归算法，我们可以毫无疑问地声明无需使用迭代就可以完成数组的反转。

其他背景信息
迭代，递归实现和递归算法之间的区别

一个普遍的误解是，递归实现意味着算法是递归的。它们不相等。这是关于原因的权威解释，其中包括上述解决方案的详细解释。

什么是迭代和递归？

早在1990年，计算机科学领域的三位最受尊敬的现代算法分析学者Thomas H.
Cormen
，Charles
E.
Leiserson和Ronald
L.Rivest发表了备受赞誉的
算法概论
。这本书代表了200多种受人尊敬的教科书本身的汇集，并且在20多年来，它被用作世界上大多数顶尖大学的算法教学的第一本也是唯一的本本。
。Cormen，Leiserson和Rivest对于什么构成迭代和什么构成 递归明确了 。

在分析和比较两种经典排序算法（ 插入排序 和 合并排序）时 ，他们解释了迭代算法和递归算法的基本属性（有时将增量
算法用于在相同上下文中使用经典数学迭代概念时消除歧义）。

首先，插入排序被归类为迭代算法，其行为总结如下：

对子数组A [ 1..j -1] 进行排序后，我们将单个项A [ j ]插入其适当的位置，从而得到排序后的数组A [ 1..j ]。

资料来源：
算法导论
-Cormen，Leisersen，Rivest，1990年MIT出版社

该语句将迭代算法归类为一种算法，该算法依赖于算法的先前执行（“迭代”）的结果或状态，然后将这些结果或状态信息用于解决当前迭代的问题。

另一方面，合并排序被归类为递归算法。递归算法符合称为 分而治之
的处理范式，该范式是将递归算法与非递归算法的操作区分开的三个基本标准的集合。如果在处理给定问题的过程中算法可以被认为是递归的：
1. 该问题分为[两个或多个]子问题，其中每个子问题都小于，但可以通过与原始问题（ Divide ）类似的方式解决。
2. 该问题分为[两个或多个]子问题，其中每个子问题都可以递归解决，或者如果足够小则可以直接解决（ Conquer ）。
3. 该问题分为[两个或多个]子问题，这些子问题的结果被合并以给出原始问题的解决方案（ Combine ）。
参考：算法简介
-Cormen，Leisersen，Rivest，1990年，麻省理工学院出版社

迭代算法和递归算法都将继续其工作，直到达到 终止条件 为止。插入排序中的终止条件是第 j 个项目已正确放置在数组A [1 .. j
]中。分而治之算法中的终止条件是范式的条件2“自下而上”时，即子问题的大小达到足够小的大小，因此无需进一步细分即可解决。

重要的是要注意，分而治之范式要求子问题必须以与原始问题相似的方式解决，以允许递归。由于原始问题是没有外部依赖项的独立问题，因此，子问题也必须可以解决，就好像它们是没有外部依赖项的独立问题一样，
尤其是在其他子问题上 。这意味着分而治之算法中的子问题应该自然独立。

相反，同样重要的是要注意，迭代算法的输入基于算法的先前迭代，因此必须按顺序进行考虑和处理。这在迭代之间创建依赖关系，从而阻止算法将问题划分为可以递归解决的子问题。例如，在“插入排序”中，不能将项目A
[ 1..j ]划分为两个子集，以便在所有项目A [ 1..j -1 之前确定A [ j ] 数组中的排序位置]已放置，因为A [ j。 ]
的实际正确位置可能会在A [1 .. j -1]本身放置时移动。 __

递归算法与递归实现

对术语递归的普遍误解源自一个普遍和错误的假设，即某些任务的递归实现自动表示该问题已由递归算法解决。递归算法与递归
实现不同， 而且从未如此。

递归实现涉及一个函数或一组函数，这些函数最终会调用自己，以便以与解决整个任务完全相同的方式来解决整个任务的子部分。发生递归算法
（即，那些满足Divide and
Conquer范式的应用程序，很适合递归实现。但是，递归算法可以仅使用像for(...)和这样的迭代构造来实现，while(...)因为所有算法（包括递归算法）最终都会重复执行某些任务以获取结果。

这篇文章的其他贡献者已经完美地证明了可以使用递归函数来实现迭代算法。实际上，对于涉及迭代直到满足某些终止条件的 所有事情 ，递归实现都是可能的。在基础
算法中没有除法或合并步骤的递归实现等效于具有标准终止条件的迭代实现。

以插入排序为例，我们已经知道（并且已经证明）插入排序是一种迭代算法。但是，这不会阻止插入排序的递归实现
。实际上，可以很容易地创建一个递归实现，如下所示：
```
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
```
可以看出，实现是递归的。但是，插入排序是一种迭代算法，我们知道这一点。因此，我们怎么知道即使使用上述递归实现，我们的插入排序算法也没有递归？让我们将分而治之范式的三个标准应用于我们的算法并进行检查。
1. 该问题分为[两个或多个]子问题，其中每个子问题都小于原始问题，但可以通过与原始问题类似的方式解决。
是：不包括长度为1的数组，将项A [ j ]插入到数组中其适当位置的方法与将所有先前项A [ 1..j -1]插入到数组中的方法相同。
1. 该问题分为[两个或更多]子问题，其中每个子问题都是独立的，可以递归解决，或者如果足够小则可以直接解决。
否：项A [ j ]的正确放置完全 取决于 包含A [1 .. j
-1]项和要排序的项的数组。因此，在处理数组的其余部分之前，不会将项A [ j ]（称为 itemToSort ）放入数组中。
1. 该问题分为[两个或多个]子问题，这些子问题的结果被合并以给出原始问题的解决方案。
否：作为一种迭代算法，在任何给定的迭代中只能正确放置一项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
```
这是一个纯粹的迭代算法。让我们检查一下为什么可以通过将其与确定算法的 递归性 的分而治之范式进行比较得出结论。
1. 该问题分为[两个或多个]子问题，其中每个子问题都小于原始问题，但可以通过与原始问题类似的方式解决。
是：将数组的反转分解为最细粒度的元素，每个元素的处理与所有其他已处理元素相同。
1. 该问题分为[两个或更多]子问题，其中每个子问题都是独立的，可以递归解决，或者如果足够小则可以直接解决。
是：数组中元素 i的反转是可能的，而无需元素 （i +1） （例如）是否已反转。此外，数组中元素 i的
反转不需要其他元素反转的结果即可完成。
1. 该问题分为[两个或多个]子问题，这些子问题的结果被合并以给出原始问题的解决方案。
否：作为一种迭代算法，每个算法步骤仅执行一个计算阶段。它不会将问题分成子问题，并且不会合并两个或多个子问题的结果来得到结果。

上面我们第一个算法的analsys证实它不适合分而治之范式，因此不能被认为是递归算法。但是，由于同时满足了标准（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
```
如您所见，该算法将问题分解为多个子问题，直到达到给出即时结果的最佳子问题粒度为止。然后在合并结果时反转结果以提供反转的结果数组。尽管我们认为该算法是递归的，但让我们将三个critera应用于分而治之算法进行确认。
1. 该问题分为[两个或多个]子问题，其中每个子问题都小于原始问题，但可以通过与原始问题类似的方式解决。
是：可以使用与2、3、4或5级完全相同的算法反转1级的阵列。
1. 该问题分为[两个或更多]子问题，其中每个子问题都是独立的，可以递归解决，或者如果足够小则可以直接解决。
是
：通过将问题分成两个独立的子数组并递归地反转这些子数组，可以解决每个非单位长度的子问题。单位长度数组（可能的最小数组）本身会颠倒过来，从而提供了终止条件并保证了第一组合并结果。
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
```
这类似于其他张贴者提出的解决方案。这是一种递归 实现， 因为定义的函数最终会调用自身以对数组中的所有元素重复执行相同的任务。然而，这并没有使
算法
递归的，因为没有问题为子问题划分，并没有子问题的结果进行合并，得到最终的结果。在这种情况下，递归只是用作流控制构造，并且在算法上，可以证明总体结果与针对该方法提出的原始迭代算法以完全相同的顺序执行了相同的步骤序列。解。

那就是 迭代算法 ， 递归算法 和 递归实现 之间的区别。

知识点

algorithm

面圈网VIP题库全新上线，海量真题题库资源。 90大类考试，超10万份考试真题开放下载啦

去下载看看