How to make this recursive function iterative in python?

Question

Usually I'm good with this type of thing, but this is bugging me. I had to write this function last week, and writing it recursively made the most sense, although now I'm trying to find a way to make it iterative to incorporate it into another function I'm writing. This is the recursive version of the function,

def XXX (x,y,z):
    if z[x][0][0] != z[y][0][0]:
        XXX(z[x][0],z[y][0],z)
    else:
        return z[x][0]

and this is the data structure

{'A': [('AD', 4.0), None, None], 'C': [('ADBFGC', 14.5), None, None], 'B': [('BF', 0.5), None, None], 'E': [('ADBFGCE', 17.0), None, None], 'D': [('AD', 4.0), None, None], 'G': [('BFG', 6.25), None, None], 'F': [('BF', 0.5), None, None], 'ADBFG': [('ADBFGC', 6.25), ('AD', 4.25), ('BFG', 2.0)], 'BF': [('BFG', 5.75), ('B', 0.5), ('F', 0.5)], 'ADBFGC': [('ADBFGCE', 2.5), ('ADBFG', 6.25), ('C', 14.5)], 'ADBFGCE': [None, ('ADBFGC', 2.5), ('E', 17.0)], 'BFG': [('ADBFG', 2.0), ('BF', 5.75), ('G', 6.25)], 'AD': [('ADBFG', 4.25), ('A', 4.0), ('D', 4.0)]}

I'm completely blanking on this, any help would be appreciated :)

does this recursion (or loop in the case of answer) always end? Without analyzing it too deeply it seems to me that it is simple to create a tree which will cause an infinite recursion/loop (the condition check for "tree ended, no common ancestor" is missing) — ShinTakezou
– ShinTakezou, Commented Apr 3, 2012 at 5:12

ninjagecko · Accepted Answer · 2012-04-03 05:07:23Z

1

def ClosestCommonAncestor(otu1, otu2, tree):
    while tree[otu1][0][0] != tree[otu2][0][0]:
        otu1,otu2,tree = tree[otu1][0],tree[otu2][0],tree
    return tree[otu1][0]

Do note that it should be possible to add functionality to the recursive version. I would also suggest defining a Tree(*children) class to make things clearer.

answered Apr 3, 2012 at 5:07

ninjagecko

91.5k24 gold badges144 silver badges153 bronze badges

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

1 Comment

ninjagecko Over a year ago

For the record: this function will not find the ClosestCommonAncestor; it was just named that. I believe the OP realized this and has since edited his question.

Raymond Hettinger · Accepted Answer · 2012-04-03 05:20:16Z

1

def ClosestCommonAncestor (otu1,otu2,tree):
    while True:
        a = tree[otu1][0]
        b = tree[otu2][0]
        if a[0] == b[0]:
            return a
        otu1 = a
        otu2 = b

answered Apr 3, 2012 at 5:20

Raymond Hettinger

229k67 gold badges405 silver badges504 bronze badges

1 Comment

TheFoxx Over a year ago

I like this function, it's returning a strange error though, KeyError: ('AD', 4.0)

Collectives™ on Stack Overflow

How to make this recursive function iterative in python?

2 Answers 2

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related