nEO - 7 months ago 32
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:
allProducts.append(a*b*c*d)
``````

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.

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`.

Source (Stackoverflow)