nEO - 1 year ago 51

Python Question

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.

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`

.