python - python递归问题

Question

我有以下用 python 2.7 编写的代码，用于查找集合 (AxAxA...xA) 的 n 次笛卡尔积-

prod=[]
def cartesian_product(set1,set2,n):
    if n>=1:
        for x in set1:
            for y in set2:
                prod.append('%s,%s'%(x,y))
        #prod='[%s]' % ', '.join(map(str, prod)) 
        #print prod
        cartesian_product(set1,prod,n-1)
    else:
        print prod


n=raw_input("Number of times to roll: ")
events=["1","2","3","4","5","6"]
cartesian_product(events,events,1)

这在 n=1 时正常工作。但是将参数值从 cartesian_product(events,events,1) 更改为 cartesian_product(events,events,2) 不起作用。似乎有一个无限循环正在运行。我不知道我到底在哪里犯了错误。

Answer 1

当您将对全局变量 prod 的引用传递给递归调用时，您正在修改 set2 也引用的列表。这意味着 set2 会随着您对其进行迭代而增长，这意味着迭代器永远不会到达终点。

这里不需要全局变量。 返回计算的产品。

def cartesian_product(set1, n):
    # Return a set of n-tuples
    rv = set()
    if n == 0:
        # Degenerate case: A^0 == the set containing the empty tuple
        rv.add(())
    else:
        rv = set()
        for x in set1: 
            for y in cartesian_product(set1, n-1):
                rv.add((x,) + y)
    return rv

如果您想保留原始参数的顺序，请改用 rv = [] 和 rv.append。