<blockquote>
<p>I am not allowed to use the built-in function <code>zip</code> and must use recursion.</p>
</blockquote>
<p>这是不幸的。你的教授或讲师(为假设这是一个学术项目而道歉;如果不是,同样的观点也适用)迫使你误用递归。这就像试图用一瓶香槟而不是灭火器来灭火一样。完成课程后,请使用内置和迭代</p>
<p>一般来说,迭代几乎总是Python中列表操作的正确工具。在<a href="https://stackoverflow.com/questions/66842109/recursion-applied-to-lists-vs-trees-in-python/66846438#66846438">recursion is actually suitable</a>中还有其他问题,比如遍历树,因为递归步骤通过次线性因子分解问题。这里没有分裂和征服</p>
<p>递归不能很好地替代迭代的一些原因:</p>
<ul>
<li>每个递归调用都需要额外的计算工作来分配和销毁循环不需要的调用帧</李>
<li>默认情况下,CPython的递归限制为1000左右,因此如果列表长度超过1000(对于任何非平凡的应用程序,列表长度都会超过1000),则程序将崩溃。您不能无限期地扩展调用堆栈大小,因此<a href="https://docs.python.org/3/library/sys.html#sys.setrecursionlimit" rel="nofollow noreferrer">^{<cd1>}</a>是一种不安全的黑客行为</李>
<li>调用帧之间不共享状态,因此您不得不做一些丑陋的事情,比如向参数添加索引,或者在每次调用时用一个切片复制整个<em>列表(就像您正在做的那样),在最坏的情况下会导致不必要的二次复杂度(就像这里的情况)或者只是笨拙的代码(例如,如果您想要构建一个结果列表,这里就是这样)</li>
</ul>
<p><a href="https://en.wikipedia.org/wiki/Functional_programming" rel="nofollow noreferrer">Some languages</a>支持<a href="https://en.wikipedia.org/wiki/Tail_call" rel="nofollow noreferrer">tail call optimization</a>,自然适合编写这样的算法,但是<a href="https://stackoverflow.com/questions/1017621/why-isnt-python-very-good-for-functional-programming">Python isn't one of them</a></p>
<p>也就是说,我知道这是一个教学练习,所以让我们一起来学习递归</p>
<hr/>
<p>在开始之前,我还想提供一些一般的编程技巧</p>
<p>当你被困在一个算法上时,试着简化这个问题。看看你是否可以合并两个长度相等的列表,然后,一旦开始工作,增加额外的列表长度不同的要求。这将消除对一个列表为空而另一个不为空的检查,并且通常使问题更容易理解。当您着手解决整个问题时,您已经拥有了子问题的最少工作代码,以及在较小的问题空间中解决问题所获得的经验和模式</p>
<p>这里的代码看起来像是你已经跳到了前面,在没有测试的情况下编写了它,并且已经做出了一系列的决定和假设,这些决定和假设对于单独执行是没有意义的。采取更小的步骤</p>
<p>打印(或使用调试器)以检查每帧的值。在小示例上计算算法</p>
<p>基本阅读:<a href="https://ericlippert.com/2014/03/05/how-to-debug-small-programs/" rel="nofollow noreferrer">Eric Lippert - How to Debug Small Programs</a></p>
<hr/>
<p>让我们检查一下代码中的一些小问题,然后构建更大的问题</p>
<blockquote>
<p>Does the order of the <code>elif</code> and such matter?</p>
</blockquote>
<p>如果分支条件都不相交,则顺序无关紧要,如:</p>
<pre class="lang-py prettyprint-override"><code>if foo == "a": return 0
if foo == "b": return 1
if foo == "c": return 2
</code></pre>
<p>由于<code>foo</code>不能同时是<code>"a"</code>、<code>"b"</code>和<code>"c"</code>,这些分支是互斥的。当您可以得到它时,这是一个很好的简化假设(上面的代码可以重构为表查找,完全删除条件链)</p>
<p>但是如果你有依赖的支票,比如</p>
<pre class="lang-py prettyprint-override"><code>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
</code></pre>
<p>那么顺序就很重要了。应该首先检查两个都为空的情况(您可以简单地使用<code>if lst:</code>和<code>if not lst:</code>从肾盂角度检查它们的空性)</p>
<P>考虑列表中的一个为空的情况:</P>
<pre class="lang-py prettyprint-override"><code>if len(l1) == 0:
return l2[0] + zippa(l1,l2[1:])
</code></pre>
<p>此时,您可以<code>return l2</code>当一个列表为空时,您只需返回非空的列表,而不是将其一块一块地切碎。由于分支的顺序,<code>l2</code>不能保证有一个元素,它很可能是空的</p>
<p>接下来是代码</p>
<pre class="lang-py prettyprint-override"><code>elif len(l1) == 0 and len(l2) == 0:
return 0 # ??!
</code></pre>
<p>具有不一致的类型。我们正在尝试返回一个列表,因此两个空列表的基本大小写合并为一个空列表,而不是整数0。这应该是<code>return []</code>,因此调用方在两个列表上使用<code>+</code>来连接nate它们,而不是<code>[] + 0</code>,这会引发类型错误。类型化语言不允许您编写此代码,即使在动态类型化语言中,混合类型通常也是一种反模式,即使在它工作时也是如此</p>
<p>在主递归案例代码中,切片<code>l1[1:0]</code>总是给出一个空列表。将问题分解为一小块,并在repl中尝试验证我们的假设,我们看到:</p>
<pre class="lang-py prettyprint-override"><code>>>> [1,2,3][1:0]
[]
</code></pre>
<p>显然,这不是你想要的。看起来您正试图在这里对“交替”模式进行编码,因此您可能只想将第一个元素切掉作为列表:</p>
<pre class="lang-py prettyprint-override"><code>>>> [1,2,3][0:1]
[1]
>>> [1,2,3][:1]
[1]
</code></pre>
<p>其次,我不清楚<code>zippa(l1[:1],l2) + zippa(l1,l2[:1])</code>模式如何工作。我们有一个无限循环,因为第一个元素一旦存在,就永远不会被任何逻辑删除。对于线性列表算法,生成多个递归调用并合并结果不是必需的。在一次调用中合并两个列表中的一个元素似乎是最容易的。递归中没有规则说不能合并</p>
<p>回到切片,这是不必要的二次复杂度,需要做很多额外的工作才能使算法递归工作。我们可以通过将索引作为第三个参数传递到递归调用中来解决复杂性问题和切片问题。这可以是默认参数,也可以添加到内部或辅助函数中</p>
<p>作为使代码更简单的最后一个优化点:列表上的每个<code>+</code>操作符分配一个全新的列表!如果我们在每一帧上都这样做,我们就回到了二次复杂度。如果要对任何<a href="https://en.wikipedia.org/wiki/Merge_sort" rel="nofollow noreferrer">nontrivial purpose</a>可用,合并列表必须只涉及固定数量的分配(最好是一个)。这可以通过在递归调用中传递一个结果列表来完成,在第一次调用中分配一次</p>
<p>代码如下:</p>
<pre class="lang-py prettyprint-override"><code>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
</code></pre>
<p>如果您不喜欢向调用者公开这些参数,请使用内部或辅助函数,这是典型的递归:</p>
<pre class="lang-py prettyprint-override"><code>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
</code></pre>
<p>请注意,虽然我正在切片,但它是一次性的基本情况,因此这是恒定的复杂性(并且一个或两个切片都是空的)。您可以使用传统的<code>range</code>循环来避免这些分配,但这是过早的优化</p>
<hr/>
<p>虽然它不是你作业的一部分,但像这样的算法应该推广到任意数量的列表。通过添加一个循环,这很容易:</p>
<pre class="lang-py prettyprint-override"><code>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
</code></pre>
<p>这里的时间和空间复杂性为O(nm)</p>
<p>最后,<a href="https://www.python.org/dev/peps/pep-0255/" rel="nofollow noreferrer">generators</a>是一种处理像这样的可移植算法的Pythonic方法<code>itertools</code>什么都使用生成器,这样做很好。生成器为调用者提供了最大的灵活性:它们可以使用相同的算法来合并,比如说,iterable的前半部分,或者随着时间的推移,以节省内存的方式惰性地进行合并(这些用例是您希望算法使用常量空间的动机的一部分!)</p>
<pre class="lang-py prettyprint-override"><code>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]
</code></pre>
<hr/>
<p>毕竟,对于递归来说,这仍然是一个做作且糟糕的用例(如果有任何悬而未决的疑问,请在1000个元素的列表上尝试),因此您可能希望在规范线程<a href="https://stackoverflow.com/questions/3678869/pythonic-way-to-combine-two-lists-in-an-alternating-fashion/69057908#69057908">Pythonic way to combine two lists in an alternating fashion?</a>中看到我建议的问题解决方案</p>
<p>让我们<a href="https://stackoverflow.com/questions/2866380/how-can-i-time-a-code-segment-for-testing-performance-with-pythons-timeit/62865237#62865237">benchmark</a>这个答案中的一些代码,以及这个答案中的代码和<a href="https://stackoverflow.com/a/69058378/6243352">the quadratic solution given in this other answer</a></p>
<pre class="lang-py prettyprint-override"><code>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")
</code></pre>
<p>尽管有一个不幸的限制,即我们不能使用超过一千个元素的更大测试(啊!递归!),但结果是清楚的:内置函数破坏了递归方法,二次函数不能按预期扩展,即使是在很小的输入上(现实世界的可比性通常可以是几十万、数百万或数十亿个元素或更多):</p>
<pre class="lang-none prettyprint-override"><code>
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
</code></pre>