## Recursive function, how?

This is the place for queries that don't fit in any of the other categories.

### Recursive function, how?

Dear all,

I know it is not wise to work with recursive functions, but I think I need one. I have two vectors (arrays: state1, state2) and would like to interpolate in between with a certain step size (array: step). For three dimensions this function works:

Code: Select all
`def recurse(state1, state2, step):  var1 =  state1[0]  while var1 <=  state2[0]:    var2 =  state1[1]    while var2 <=  state2[1]:      var3 = state1[2]      while var3 <=  state2[2]:        print var1,var2,var3        var3 *= step[2]      var2 += step[1]       var1 += step[0]`

However, I will need to use vectors up to dimension 30. Moreover, the first two dimensions are additive and the rest are multiplicative.
How could I generalize these nested loops to a flexible recursive function?

Peter
pnemeth

Posts: 3
Joined: Tue Mar 12, 2013 10:29 am

### Re: Recursive function, how?

pnemeth wrote:I know it is not wise to work with recursive functions

Not always. You have to be careful when dealing with recursion, but sometime recursion provides the most elegant solution.
pnemeth wrote:but I think I need one

Nope, in this case, recursion isn't necessary:
Code: Select all
`from operator import add, mulexample_state1 = [1,2,3]example_state2 = [10,30,24]example_steps = [3,5,2]example_ops = [add,add,mul]def interpolate(state1, state2, steps, ops):    results = []    for v1, v2, s, o in zip(state1, state2, steps, ops):        r = []        v = v1        while v <= v2:            r.append(v)            v = o(v,s)        results.append(r)    return resultsif __name__=='__main__':    results = interpolate(example_state1, example_state2, example_steps, example_ops)    from pprint import pprint    pprint(results)`

Note that this function makes two assumptions about its inputs: that all input lists are of the same length, and that the values in state2 are always greater or equal to the values in state1 for a positive step, and that this solution will not work for negative steps, as that will result in oscillation between positive and negative values in case of multiplication, which would break the while check. Also note that if you were dealing with additive interpolation only, a better way to implement that would be with Python's built-in range() function, i.e. results.append(range(v1, v2, s)) instead of the while loop.
setrofim

Posts: 288
Joined: Mon Mar 04, 2013 7:52 pm

### Re: Recursive function, how?

Hi Setrofim,

Thanks for your reply and for looking into my problem! I forgot about "zip", it is really handy here. Now I am closer to a solution. However, using your example, your code returns this list:

Code: Select all
`[[1, 4, 7, 10], [2, 7, 12, 17, 22, 27], [3, 6, 12, 24]]`

Code: Select all
`1 2 31 2 61 2 121 2 241 7 31 7 61 7 121 7 241 12 31 12 61 12 121 12 241 17 31 17 61 17 121 17 241 22 31 22 61 22 121 22 241 27 31 27 61 27 121 27 244 2 34 2 64 2 124 2 244 7 34 7 64 7 124 7 244 12 34 12 64 12 124 12 244 17 34 17 64 17 124 17 244 22 34 22 64 22 124 22 244 27 34 27 64 27 124 27 247 2 37 2 67 2 127 2 247 7 37 7 67 7 127 7 247 12 37 12 67 12 127 12 247 17 37 17 67 17 127 17 247 22 37 22 67 22 127 22 247 27 37 27 67 27 127 27 2410 2 310 2 610 2 1210 2 2410 7 310 7 610 7 1210 7 2410 12 310 12 610 12 1210 12 2410 17 310 17 610 17 1210 17 2410 22 310 22 610 22 1210 22 2410 27 310 27 610 27 1210 27 24`

So I still need to loop through all the dimensions. This is why I tried with recursion in the first place. What do you think?

cheers,
Peter
pnemeth

Posts: 3
Joined: Tue Mar 12, 2013 10:29 am

### Re: Recursive function, how?

itertools.product does exactly what you need:
Code: Select all
`from operator import add, mulfrom itertools import productexample_state1 = [1,2,3]example_state2 = [10,30,24]example_steps = [3,5,2]example_ops = [add,add,mul]def interpolate(state1, state2, steps, ops):    results = []    for v1, v2, s, o in zip(state1, state2, steps, ops):        r = []        v = v1        while v <= v2:            r.append(v)            v = o(v,s)        results.append(r)    return product(*results)if __name__=='__main__':    results = interpolate(example_state1, example_state2, example_steps, example_ops)    for  r in results:        print ' '.join(map(str,r))`
setrofim

Posts: 288
Joined: Mon Mar 04, 2013 7:52 pm

### Re: Recursive function, how?

Yes, yes, this is it and not least, it is fast.
Thank you!
pnemeth

Posts: 3
Joined: Tue Mar 12, 2013 10:29 am