Python基础教程 递归条件

9.8.6 递归条件

现在来看看这个解决方案的递归部分。处理好基线条件后，可在递归条件中假设来自更低层级（编号更大的皇后）的结果都是正确的。因此，只需在函数queens的前述实现中给if语句添加一个else子句。

你希望递归调用返回什么样的结果呢？你希望它返回当前行下面所有皇后的位置，对吧？假设位置是以元组的方式返回的，因此需要修改基线条件，使其返回一个（长度为1的）元组，但这将在后面处理。

因此，对于递归调用，向它提供的是由当前行上面的皇后位置组成的元组。对于当前皇后的每个合法位置，递归调用返回的是由下面的皇后位置组成的元组。为了让这个过程不断进行下去，只需将当前皇后的位置插入返回的结果开头，如下所示：

...

else:

for pos in range(num):

if not conflict(state, pos):

for result in queens(num, state + (pos,)):

yield (pos,) + result

这里的for pos和if not conflict部分与前面相同，因此可以稍微简化一下代码。另外，还可给参数指定默认值。

def queens(num=8, state=()):

for pos in range(num):

if not conflict(state, pos):

if len(state) == num-1:

yield (pos,)

else:

for result in queens(num, state + (pos,)):

yield (pos,) + result

如果你觉得这些代码难以理解，用自己的话来描述其作用可能会有所帮助。另外，你可能还记得(pos,)中的逗号必不可少（不能仅用圆括号将pos括起），这样得到的才是元组。

生成器queens提供了所有的解（即所有合法的皇后位置组合）。

>>> list(queens(3))

[]

>>> list(queens(4))

[(1, 3, 0, 2), (2, 0, 3, 1)]

>>> for solution in queens(8):

... print solution

...

(0, 4, 7, 5, 2, 6, 1, 3)

(0, 5, 7, 2, 6, 3, 1, 4)

...

(7, 2, 0, 5, 1, 4, 6, 3)

(7, 3, 0, 2, 5, 1, 6, 4)

>>>

如果运行queens时将参数num设置为8，将快速显示大量的解。下面看看有多少个解。

>>> len(list(queens(8)))

92