使用递归合并两个列表

Question

我想把两个不同长度的列表中的其他元素合并到一个列表中。我不允许使用内置函数zip，必须使用递归

从print(zippa([1, 3, 5], [ 2, 4, 6, 8, 10]))开始，结果应该是：[1, 2, 3, 4, 5, 6, 8, 10]

这是我目前的代码：

def zippa(l1, l2): 
    if len(l1) == 0:
        return l2[0] + zippa(l1,l2[1:])
    elif len(l2) == 0:
        return l1[0] + zippa(l1[1:],l2)
    elif len(l1) == 0 and len(l2) == 0:
        return 0
    else:
        return zippa(l1[1:0],l2) + zippa(l1,l2[1:0])

我不明白如何将值重新放入列表中。 elif的顺序和类似的事情有关系吗

Answer 1

I am not allowed to use the built-in function zip and must use recursion.

这是不幸的。你的教授或讲师（为假设这是一个学术项目而道歉；如果不是，同样的观点也适用）迫使你误用递归。这就像试图用一瓶香槟而不是灭火器来灭火一样。完成课程后，请使用内置和迭代

一般来说，迭代几乎总是Python中列表操作的正确工具。在recursion is actually suitable中还有其他问题，比如遍历树，因为递归步骤通过次线性因子分解问题。这里没有分裂和征服

递归不能很好地替代迭代的一些原因：

• 每个递归调用都需要额外的计算工作来分配和销毁循环不需要的调用帧
• 默认情况下，CPython的递归限制为1000左右，因此如果列表长度超过1000（对于任何非平凡的应用程序，列表长度都会超过1000），则程序将崩溃。您不能无限期地扩展调用堆栈大小，因此^{}是一种不安全的黑客行为
• 调用帧之间不共享状态，因此您不得不做一些丑陋的事情，比如向参数添加索引，或者在每次调用时用一个切片复制整个列表（就像您正在做的那样），在最坏的情况下会导致不必要的二次复杂度（就像这里的情况）或者只是笨拙的代码（例如，如果您想要构建一个结果列表，这里就是这样）

Some languages支持tail call optimization，自然适合编写这样的算法，但是Python isn't one of them

也就是说，我知道这是一个教学练习，所以让我们一起来学习递归

---

在开始之前，我还想提供一些一般的编程技巧

当你被困在一个算法上时，试着简化这个问题。看看你是否可以合并两个长度相等的列表，然后，一旦开始工作，增加额外的列表长度不同的要求。这将消除对一个列表为空而另一个不为空的检查，并且通常使问题更容易理解。当您着手解决整个问题时，您已经拥有了子问题的最少工作代码，以及在较小的问题空间中解决问题所获得的经验和模式

这里的代码看起来像是你已经跳到了前面，在没有测试的情况下编写了它，并且已经做出了一系列的决定和假设，这些决定和假设对于单独执行是没有意义的。采取更小的步骤

打印（或使用调试器）以检查每帧的值。在小示例上计算算法

基本阅读：Eric Lippert - How to Debug Small Programs

---

让我们检查一下代码中的一些小问题，然后构建更大的问题

Does the order of the elif and such matter?

如果分支条件都不相交，则顺序无关紧要，如：

if foo == "a": return 0
if foo == "b": return 1
if foo == "c": return 2

由于foo不能同时是"a"、"b"和"c"，这些分支是互斥的。当您可以得到它时，这是一个很好的简化假设（上面的代码可以重构为表查找，完全删除条件链）

但是如果你有依赖的支票，比如

if len(l1) == 0:
    pass # l1 must be empty; l2 may or may not be
elif len(l2) == 0:
    pass # l2 must be empty and l1 is known to be nonempty
         # or the `len(l1) == 0` branch would have been taken
elif len(l1) == 0 and len(l2) == 0:
    pass # unreachable, we've already covered cases
         # where one or the other was empty

那么顺序就很重要了。应该首先检查两个都为空的情况（您可以简单地使用if lst:和if not lst:从肾盂角度检查它们的空性）

考虑列表中的一个为空的情况：

if len(l1) == 0:
    return l2[0] + zippa(l1,l2[1:])

此时，您可以return l2当一个列表为空时，您只需返回非空的列表，而不是将其一块一块地切碎。由于分支的顺序，l2不能保证有一个元素，它很可能是空的

接下来是代码

elif len(l1) == 0 and len(l2) == 0:
    return 0 # ??!

具有不一致的类型。我们正在尝试返回一个列表，因此两个空列表的基本大小写合并为一个空列表，而不是整数0。这应该是return []，因此调用方在两个列表上使用+来连接nate它们，而不是[] + 0，这会引发类型错误。类型化语言不允许您编写此代码，即使在动态类型化语言中，混合类型通常也是一种反模式，即使在它工作时也是如此

在主递归案例代码中，切片l1[1:0]总是给出一个空列表。将问题分解为一小块，并在repl中尝试验证我们的假设，我们看到：

>>> [1,2,3][1:0]
[]

显然，这不是你想要的。看起来您正试图在这里对“交替”模式进行编码，因此您可能只想将第一个元素切掉作为列表：

>>> [1,2,3][0:1]
[1]
>>> [1,2,3][:1]
[1]

其次，我不清楚zippa(l1[:1],l2) + zippa(l1,l2[:1])模式如何工作。我们有一个无限循环，因为第一个元素一旦存在，就永远不会被任何逻辑删除。对于线性列表算法，生成多个递归调用并合并结果不是必需的。在一次调用中合并两个列表中的一个元素似乎是最容易的。递归中没有规则说不能合并

回到切片，这是不必要的二次复杂度，需要做很多额外的工作才能使算法递归工作。我们可以通过将索引作为第三个参数传递到递归调用中来解决复杂性问题和切片问题。这可以是默认参数，也可以添加到内部或辅助函数中

作为使代码更简单的最后一个优化点：列表上的每个+操作符分配一个全新的列表！如果我们在每一帧上都这样做，我们就回到了二次复杂度。如果要对任何nontrivial purpose可用，合并列表必须只涉及固定数量的分配（最好是一个）。这可以通过在递归调用中传递一个结果列表来完成，在第一次调用中分配一次

代码如下：

def merge_iterables(a, b, i=0, result=None): 
    if result is None:
        result = []

    if i < len(a) and i < len(b):
        result.append(a[i])
        result.append(b[i])
        merge_iterables(a, b, i + 1, result)
    else:
        result.extend(a[i:])
        result.extend(b[i:])

    return result

如果您不喜欢向调用者公开这些参数，请使用内部或辅助函数，这是典型的递归：

def merge_iterables(a, b):
    result = []

    def merge(i=0):
        if i < len(a) and i < len(b):
            result.append(a[i])
            result.append(b[i])
            merge(i + 1)
        else:
            result.extend(a[i:])
            result.extend(b[i:])

    merge()
    return result

请注意，虽然我正在切片，但它是一次性的基本情况，因此这是恒定的复杂性（并且一个或两个切片都是空的）。您可以使用传统的range循环来避免这些分配，但这是过早的优化

---

虽然它不是你作业的一部分，但像这样的算法应该推广到任意数量的列表。通过添加一个循环，这很容易：

def merge_iterables(*its):
    result = []

    def merge(i=0):
        for x in its:
            if i < len(x):
                result.append(x[i])

        if any(i < len(x) for x in its):
            merge(i + 1)

    merge()
    return result

这里的时间和空间复杂性为O（nm）

最后，generators是一种处理像这样的可移植算法的Pythonic方法itertools什么都使用生成器，这样做很好。生成器为调用者提供了最大的灵活性：它们可以使用相同的算法来合并，比如说，iterable的前半部分，或者随着时间的推移，以节省内存的方式惰性地进行合并（这些用例是您希望算法使用常量空间的动机的一部分！）

def merge_iterables(*its):
    def merge(i=0):
        for x in its:
            if i < len(x):
                yield x[i]

        if any(i < len(x) for x in its):
            yield from merge(i + 1)

    yield from merge()

if __name__ == "__main__":
    print(list(merge_iterables([1,2], [4,5,6,7], "a", "xyz")))
    # => [1, 4, 'a', 'x', 2, 5, 'y', 6, 'z', 7]

---

毕竟，对于递归来说，这仍然是一个做作且糟糕的用例（如果有任何悬而未决的疑问，请在1000个元素的列表上尝试），因此您可能希望在规范线程Pythonic way to combine two lists in an alternating fashion?中看到我建议的问题解决方案

让我们benchmark这个答案中的一些代码，以及这个答案中的代码和the quadratic solution given in this other answer

import argparse
import copy
import dis
import inspect
import random
import sys
import timeit
from itertools import zip_longest

sys.setrecursionlimit(1350) # just for testing

def merge_pythonic(*its):
    return [x for y in zip_longest(*its) for x in y if x is not None]

def merge_iterables(*its):
    result = []

    def merge(i=0):
        for x in its:
            if i < len(x):
                result.append(x[i])

        if any(i < len(x) for x in its):
            merge(i + 1)

    merge()
    return result

def zippa(*its):
    if len(its) == 0:
        return []
    
    head_list, *rest_its = its
    
    if head_list:
        head, *rest = head_list
        return [head] + zippa(*rest_its, rest)
    else:
        return zippa(*rest_its)

if __name__ == "__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument(" n", type=int, default=1300)
    parser.add_argument(" m", type=int, default=1300)
    parser.add_argument(" trials", type=int, default=1000)
    parser.add_argument(" dis", action="store_true")
    args = parser.parse_args()
    n = args.n
    m = args.m
    trials = args.trials
    namespace = dict(its=[random.sample(range(n), k=n) for _ in range(m)])
    funcs_to_test = [x for x in locals().values() 
                     if callable(x) and x.__module__ == __name__]
    print(f"{'-' * 30}\nn = {n}, {trials} trials\n{'-' * 30}\n")

    for func in funcs_to_test:
        fname = func.__name__
        fargs = ", ".join(inspect.signature(func).parameters)
        stmt = f"{fname}({fargs})"
        setup = f"from __main__ import {fname}"
        time = timeit.timeit(stmt, setup, number=trials, globals=namespace)
        print(inspect.getsource(globals().get(fname)))

        if args.dis:
            dis.dis(globals().get(fname))

        print(f"time (s) => {'%.16f' % time}\n{'-' * 30}\n")

尽管有一个不幸的限制，即我们不能使用超过一千个元素的更大测试（啊！递归！），但结果是清楚的：内置函数破坏了递归方法，二次函数不能按预期扩展，即使是在很小的输入上（现实世界的可比性通常可以是几十万、数百万或数十亿个元素或更多）：

               
n = 1300, m = 1300, 1000 trials
               

def merge_pythonic(*its):
    return [x for y in zip_longest(*its) for x in y if x is not None]

time (s) => 0.4278396000000000
               

def merge_iterables(*its):
    result = []

    def merge(i=0):
        for x in its:
            if i < len(x):
                result.append(x[i])

        if any(i < len(x) for x in its):
            merge(i + 1)

    merge()
    return result

time (s) => 4.4487939000000001
               

def zippa(*its):
    if len(its) == 0:
        return []

    head_list, *rest_its = its

    if head_list:
        head, *rest = head_list
        return [head] + zippa(*rest_its, rest)
    else:
        return zippa(*rest_its)

time (s) => 40.0880948000000004
               

Answer 2

处理列表递归的一种经典方法是将列表的头部分拆分，然后对其余部分进行处理。这是一种在函数语言中随处可见的模式，它使递归成为一级公民。它在Python中不是一流的公民，但您仍然可以使用Python来学习这些技术

这里我们制作了一个函数，可以压缩任意数量的列表。这很方便，因为一旦用完了短列表，就可以继续调用它，直到不再有没有大量if/else的列表

def zippa(*lists):
    if len(lists) == 0:
        return []
    
    head_list, *rest_lists = lists
    
    if head_list:
        head, *rest = head_list
        return [head] + zippa(*rest_lists, rest)
    else:
        return zippa(*rest_lists)
    
print(zippa([1, 3, 5], [ 2, 4, 6, 8, 10])) 

这个作业中唯一真正复杂的是你要处理多个列表。但想法是一样的，每个调用负责获取第一个列表，然后从列表中获取第一个元素。然后返回带有递归结果的元素

这是通过在递归时旋转列表来实现的。通过在last:zippa(*rest_lists, rest)中传递原始第一个列表的其余部分

这与精心选择的基本情况一起允许您传入任意数量的列表，从而使代码更简单。您不必处理索引或辅助参数

# works with a single list
print(zippa([1, 3, 5]) )
# [1, 3, 5]

# or multiple:
print(zippa([1, 3, 5], [ 2, 4, 6, 8, 10], [0, 0, 0, 0])) 
# [1, 2, 0, 3, 4, 0, 5, 6, 0, 8, 0, 10]