nEO nEO - 1 year ago 55
Python Question

Converting a for loop to recursion in Python

I am new to recursion and am trying to convert a for loop to recursion.

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:

I am not able to convert this to a recursive program, which means I am not able to scale up. The idea is this - define a recursive program in Python that takes input A (number of for loops) and B (number which is a divisor of the product).

Any help would be really helpful.

Answer Source

You can use itertools.product and its repeat argument:

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))

Changing the repeat argument of myprod will change the number of loops and factors you are calculating.

Also, since multiplication is commutative (a * b == b * a) you should eliminate repetitive computations using 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))

If you remove duplicate results from myprod using set you will find that the two results are equal:

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

but you have cut down the number of operations drastically from n ** r to (n+r-1)! / r! / (n-1)!. For example 92,378 instead of 10,000,000,000 for n=10, r=10.