python - 在 Python 中将 for 循环转换为递归

Question

我是递归新手，正在尝试将 for 循环转换为递归。

allProducts = []

for a in range(10):
    for b in range(10):
        for c in range(10):
            for d in range(10):
                if (a*b*c*d)%6==0:
                    allProducts.append(a*b*c*d)

我无法将其转换为递归程序，这意味着我无法扩展。这个想法是这样的 - 在 Python 中定义一个递归程序，它接受输入 A(for 循环数)和 B(乘积除数的数字)。

任何帮助都会非常有帮助。

Answer 1

您可以使用itertools.product及其repeat参数:

from operator import mul
import itertools


def myprod(n, div, repeat=4):
    # i is a list of factors
    for i in itertools.product(range(n), repeat=repeat):
        # calculate product of all elements of list            
        prod = reduce(mul, i, 1)
        if prod % div == 0:
            yield prod

print list(myprod(10, 6))

更改 myprod 的 repeat 参数将更改您正在计算的循环数和因子。

此外，由于乘法是可交换的(a * b == b * a)，您应该使用 itertools.combinations_with_replacement 消除重复计算:

from operator import mul
import itertools


def myprod_unique(n, div, repeat=4):
    for i in itertools.combinations_with_replacement(range(n), r=repeat):
        prod = reduce(mul, i, 1)
        if prod % div == 0:
            yield prod

print list(myprod_unique(10, 6))

如果使用 set 从 myprod 中删除重复的结果，您会发现两个结果是相等的:

print set(myprod_unique(10, 6)) == set(myprod(10, 6))

但是您已将操作数量从 n ** r 大幅减少到 (n+r-1)!/r!/(n-1)!。例如，n=10, r=10 的值为 92,378，而不是 10,000,000,000。