Converting a for loop to recursion in 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.

I don't think recursion really is the thing you are looking for. — Nils Werner, Oct 29 '16 at 13:54
yes, finding a sum of those factors and checking if it meets a crtieria. — nEO, Oct 29 '16 at 14:01

score 2 · Answer 1 · answered Oct 29 '16 at 13:56

2

You should have a look at the builtin package itertools:

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

answered Oct 29 '16 at 13:56

dnalow

974
4
14

what happen if I need 20 or 30 of those for loops. Do I have to do this 30 times? – nEO Oct 29 '16 at 13:59
see the other answer. But I guess you will very quickly reach too large number of iterations – dnalow Oct 29 '16 at 14:03

Nils Werner · Accepted Answer · 2016-10-29T14:19:25.143

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.

thanks for all the help @nils . I am trying to understand this. One more question - in the line prod = reduce(mul,i,1) - we are multiplying all is into 1 number. Is that how I should read it? — nEO, Oct 29 '16 at 14:12
got it. And if I need to add it, I use the operator.add function instead of mul — nEO, Oct 29 '16 at 14:14

score 0 · Answer 3 · answered Oct 29 '16 at 14:22

The other answers don't use recursion. For completeness, here is one that does.

Recursive functions usually have two parts.

Base case: Handled directly. Corresponds to the body of the innermost loop in your code.
Recursive case: Involves calling the function again, corresponds to one for loop in your code.

Sometimes extra parameters need to be introduced. In this example the variables a, b, etc. that have already been set need to be passed in. The natural way to do that is using a list.

allProducts = []

def product(vals):
    res = 1
    for val in vals:
        res *= val
    return res

# n is the number of for loops remaining
# mod is the divisor
# vals is a list where the values of a, b, c, etc. will be placed
# start this function off using run(4, 6, [])
def run(n, mod, vals):
    if n == 0:
        # base case
        if product(vals) % mod == 0:
            allProducts.append(product(vals))
    else:
        # recursive case
        for i in range(10):
            # i takes the role of a, b, c, etc.
            # add i to the vals
            vals.append(i)
            # recursively iterate over remaining n-1 variables
            run(n - 1, mod, vals)
            # remove i
            vals.pop()

Converting a for loop to recursion in Python

3 Answers3