Python iterative functions

Question

I have a following function which finds distance between two trajectories, function recMethod() is the recursive function. I want to convert this recursive function to the iterative one.

def dist(pt1,pt2):
    return math.sqrt((pt2[0]-pt1[0])*(pt2[0]-pt1[0])+(pt2[1]-pt1[1])*(pt2[1]-pt1[1]))

def recMethod(ca,i,j,P,Q):
    if ca[i,j] > -1:
        return ca[i,j]
    elif i == 0 and j == 0:
        ca[i,j] = euc_dist(P[0],Q[0])
    elif i > 0 and j == 0:
        ca[i,j] = max(recMethod(ca,i-1,0,P,Q),euc_dist(P[i],Q[0]))
    elif i == 0 and j > 0:
        ca[i,j] = max(recMethod(ca,0,j-1,P,Q),euc_dist(P[0],Q[j]))
    elif i > 0 and j > 0:
        ca[i,j] = max(min(recMethod(ca,i-1,j,P,Q),recMethod(ca,i-1,j-1,P,Q),recMethod(ca,i,j-1,P,Q)),euc_dist(P[i],Q[j]))
    else:
        ca[i,j] = float("inf")
    return ca[i,j]

Please, take a look at this hande article blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html — Dmitry Belaventsev
– Dmitry Belaventsev, Commented Jun 10, 2017 at 17:12
i tried converting to tail call recursion but too many errors. — Liza
– Liza, Commented Jun 10, 2017 at 17:13

Ryan Stout · Accepted Answer · 2017-06-10 17:49:53Z

1

You just need to fill in the table ca in the right order, in this case from 0,0 to len(P)-1, len(Q)-1 One way to do it would be:

def iterative(ca, P,Q):
    ca[0,0] = euc_dist(P[0],Q[0])
    for ii in range(1,len(P)):
        ca[ii,0] = max(ca[ii-1,0], euc_dist(P[ii],Q[0]))
    for jj in range(1,len(Q)):
        ca[0,jj] = max(ca[0,jj-1], euc_dist(P[0],Q[jj]))
    for ii in range(1,len(P)):
        for jj in range(1,len(Q)):
            ca[ii,jj] = max(min(ca[ii-1,jj],
                                ca[ii-1,jj-1],
                                ca[ii,jj-1]),
                            euc_dist(P[ii],Q[jj]))
    return ca[-1,-1]

answered Jun 10, 2017 at 17:49

Ryan Stout

1,0286 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Python iterative functions

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related