CODEWITHSUNDEEP
pythonrecursionfor-loop
hAcKnRoCk
hAcKnRoCk

Reputation: 1166

Formulation of a recursive solution (variable for loops)

Please consider the below algorithm: 

  for(j1 = n upto 0)
     for(j2 = n-j1 upto 0)
       for(j3 = n-j1-j2 upto 0)
        .
         .
           for (jmax = n -j1 - j2 - j_(max-1))
            {
             count++;
             product.append(j1 * j2 ... jmax); // just an example
            }

As you can see, some relevant points about the algo snippet above:

  1. I have listed an algorithm with a variable number of for loops.
  2. The result that i calculate at each innermost loop is appended to a list. This list will grow to dimension of 'count'.

Is this problem a suitable candidate for recursion? If yes, i am really not sure how to break the problem up. I am trying to code this up in python, and i do not expect any code from you guys. Just some pointers or examples in the right direction. Thank you.

Here is an initial try for a sample case http://pastebin.com/PiLNTWED

Upvotes: 0

Views: 240

Answers (5)

hAcKnRoCk
hAcKnRoCk

Reputation: 1166

-- As a response to the excellent listing by Blckgnht -- Consider here the case of n = 2 and max = 3 

def simpletest():    

    '''
    I am going to just test the algo listing with assumption
    degree n = 2
    max = dim(m_p(n-1)) = 3, 
    so j1 j2 and upto j3 are required for every entry into m_p(degree2)
    Lets just print j1,j2,j3 to verify if the function
    works in other general version where the number of for loops is not known
    '''
    n = 2
    count = 0
    for j1 in range(n, -1, -1):
        for j2 in range(n -j1, -1, -1):
            j3 = (n-(j1+j2)) 
            count = count + 1
            print 'To calculate m_p(%d)[%d], j1,j2,j3 = ' %(n,count), j1, j2, j3

    assert(count==6)        # just a checkpoint. See P.169 for a proof
    print 'No. of entries =', count

The output of this code (and it is correct). 

    In [54]: %run _myCode/Python/invariant_hack.py
To calculate m_p(2)[1], j1,j2,j3 =  2 0 0
To calculate m_p(2)[2], j1,j2,j3 =  1 1 0
To calculate m_p(2)[3], j1,j2,j3 =  1 0 1
To calculate m_p(2)[4], j1,j2,j3 =  0 2 0
To calculate m_p(2)[5], j1,j2,j3 =  0 1 1
To calculate m_p(2)[6], j1,j2,j3 =  0 0 2
No. of entries = 6

Upvotes: 0

Blckknght
Blckknght

Reputation: 104722

Your algorithm is finding all the m-tuples (m being the max subscript of j from your pseudocode) of non-negative integers that add up to n or less. In Python, the most natural way of expressing that would be with a recursive generator:

def gen_tuples(m, n):
    if m == 0:
        yield ()
    else:
        for x in range(n, -1, -1):
            for sub_result in gen_tuples(m-1, n-x):
                yield (x,)+sub_result

Example output:

>>> for x, y, z in gen_sums(3, 3):
    print(x, y, z)

3 0 0
2 1 0
2 0 1
2 0 0
1 2 0
1 1 1
1 1 0
1 0 2
1 0 1
1 0 0
0 3 0
0 2 1
0 2 0
0 1 2
0 1 1
0 1 0
0 0 3
0 0 2
0 0 1
0 0 0

Upvotes: 1

underrun
underrun

Reputation: 6841

Typically, if you want to transform for loops into recursive calls, you will need to replace the for statements with if statements. For nested loops, you will transform these into function calls.

For practice, start with a dumb translation of the code that works and then attempt to see where you can optimize later.

To give you an idea to try to apply to your situation, I would translate something like this:

results = []
for i in range(n):
    results.append(do_stuff(i, n))

to something like this:

results = []

def loop(n, results, i=0):
    if i >= n:
        return results
    results.append(do_stuff(i, n))
    i += 1
    loop(n, results, i)

there are different ways to handle returning the results list, but you can adapt to your needs.

Upvotes: 0

jureslak
jureslak

Reputation: 194

You could also consider using permutations, combinations or product from the itertools module. If you want all the possible combinations of i, j, k, ... (i.e. nested for loops) you can use:

for p in product(range(n), repeat=depth):
    j1, j2, j3, ... = p # the same as nested for loops
    # do stuff here

But beware, the number of iterations in the loop grows exponentially!

Upvotes: 1

collapsar
collapsar

Reputation: 17238

the toy example will translate into a kind of tail recursion so, personally, i wouldn't expect a recursive version to be more insightful for code review and maintenance.

however, to get acquainted to the principle, attempt to factor out the invariant parts / common terms from the individual loop and try to identify a pattern (and best prove it afterwards!). you should be able to fix a signature of the recursive procedure to be written. flesh it out with the parts inherent to the loop body/ies (and don't forget the termination condition).

Upvotes: 0

Related Questions