我无法理解Python中递归函数的"yield

Question

我正在尝试理解“yield”。

首先，我不太明白的代码如下。

def permutations(seq):
    if len(seq) <= 1: yield seq
    else:
        for perm in permutations(seq[1:]):
            for i in range(len(perm)+1):
                yield perm[i:] + seq[0:1] + perm[:i]

print list(permutations(['police', 'buffalo', 'fish']))

结果如下：

[['fish', 'buffalo', 'police'], ['buffalo', 'police', 'fish'], ['police', 'fish', 'buffalo'], ['buffalo', 'fish', 'police'], ['fish', 'police', 'buffalo'], ['police', 'buffalo', 'fish']]

我对“yield”的理解就是它是用来生成器的。我能理解下面的代码。

def reverse(data):
    for index in range(len(data) -1, -1, -1):
        yield data[index]

for char in reverse('golf'):
    print(char)

f
l
o
g

我的理解水平就停留在上面……但是对于递归，我就不太明白了……请解释一下。谢谢。

Answer 1

你给出的代码是按照以下步骤工作的：

1. 如果序列里只有一个元素或者是空的，那么唯一的排列就是这个序列本身。
2. 把序列分成第一个元素和剩下的所有元素。
3. 根据同样的步骤考虑剩下元素的所有排列。对于每一种排列：
   1. 对于排列中的每一个位置：
      1. 在这个位置把排列分开。
      2. 把原序列的第一个元素放到这个分开的地方。这就是原序列的一种新排列。
4. 完成。

原来的代码在实现第3.1.2点时有点奇怪。我们可以通过使用更多的变量来让它更清晰一些，这里假设你在用Python 3：

def permutations(seq):
    if len(seq) <= 1: 
        yield seq 
    else:
        first, *rest = seq
        for perm in permutations(rest):
            for i in range(len(perm)+1):
                before = perm[:i]
                after = perm[i:]
                yield after + [first] + before

如你所见，最后一行把排列的开始和结束位置交换了，实际上没有什么特别的原因。它也可以直接写成 before + [first] + after，但作者选择了不这样做。这并不影响算法的工作方式——它会找到所有的排列，包括镜像的排列——但这可能导致生成的顺序有点奇怪。

---

你也可以用类似的递归生成器来实现 reverse（反转）。在这种情况下，算法是：

1. 如果序列只有一个元素或者是空的，它就是它自己的反转。
2. 把序列分成第一个元素和剩下的所有元素。
3. 用这个算法来反转剩下的元素。
4. 逐个返回上一步的结果中的每个元素。
5. 返回原序列的第一个元素。

在Python中，它看起来是这样的：

def reverse(seq):
if len(seq) <= 1:
return seq

  first, *rest = seq
  for item in reverse(rest):
       yield item
  # Or you could use:
  #  yield from reverse(rest)
  # Instead of the above loop
  yield first

Answer 2

是的，yield 是用来生成生成器的。这意味着当你调用它们时，它们会返回迭代器。生成器可以是递归的：它们可以自己调用自己，获取一个迭代器，然后对其进行迭代。在每次迭代中，它们可以根据需要返回自己的一些元素，或者不返回。

在你的例子中，permutations 是一个生成器，它总是返回一个列表的迭代器。

if len(seq) <= 1: yield seq

这很简单：在最简单的情况下，只生成一个列表，也就是 seq 本身。

for perm in permutations(seq[1:]):
        ...

这意味着“现在对不同的列表序列进行迭代”，在这个例子中，就是对第一个元素之后的所有排列的序列进行迭代。在每次迭代中，我们有一个嵌套循环，将第一个元素插入到排列的每个位置，并返回结果。

希望这能帮到你。对我来说有点难，因为我不太清楚你具体困惑的地方。

更新：提问者想知道为什么第一个结果是反向的。考虑这一行：

yield perm[i:] + seq[0:1] + perm[:i]

对于第一个结果 (i=0)，这相当于 yield perm + seq[0:1] —— 第一个元素被放到了返回列表的 末尾。通过归纳法，这个结果是 seq 的反向。如果你想要第一个结果是 ['police', 'buffalo', 'fish']，那么你可以这样做：

yield perm[:i] + seq[0:1] + perm[i:]