CODEWITHSUNDEEP
pythonrecursion
user2980081
user2980081

Reputation: 69

Recursion and Python dictionaries

I'm working through Udacity's Introduction to Computer Science Course.

For a problem set, I need to determine whether a link is reciprocal. A link from A -> B is considered reciprocal if there is k links from B -> A.

For example. if k=2, B->A would count as a reciprocal link for node A if there is a path A->C->B, for some page C, (link path of length 2), or a direct link A-> B (link path of length 1).

Here is the "internet" I'm using for the problem. It's just a dict where the key is a URL and the value is a list of links on that page. 

g = {'a': ['a', 'b', 'c'], 'b':['a','e'], 'c':['d'], 'd':['a'], 'e':['c']}

Now here is the helper function I'm working on, that ideally will return a boolean depending on whether link_a -> link_b is reciprocal. 

def is_reciprocal(g,link_a,link_b,k):
    """
    Returns True if link_a --> link_b is reciprocal
    """
    url_links = []
    print " "
    print "link_a is...",link_a
    print "link_b is...",link_b
    print "k is...",k
    print 
    if k == -1:
        return False
    for i in g[link_b]:
        if i == link_a:
            return True

    return is_reciprocal(g,link_a,g[link_b][0],k-1)

Here is the test value I am doing. 

t1 = is_reciprocal(g1,'e','c',4)

Which prints out...

link_a is... e
link_b is... c
k is... 4


link_a is... e
link_b is... d
k is... 3


link_a is... e
link_b is... a
k is... 2


link_a is... e
link_b is... a
k is... 1


link_a is... e
link_b is... a
k is... 0


link_a is... e
link_b is... a
k is... -1

It seems that when link_b is 'a', the same link_b keeps getting used.

My Question:
Is there a way to recursively sort through this dict and make link_b equivalent to all values in g['a'] while keeping the k value the same?

Upvotes: 0

Views: 268

Answers (1)

abarnert
abarnert

Reputation: 365777

It seems that when link_b is 'a', the same link_b keeps getting used.

This is not surprising, given that your recursive call explicitly only uses the first value:

return is_reciprocal(g,link_a,g[link_b][0],k-1)

If you want to use all of the values, you need to recurse on each of the values, until one of them is True. Like this:

for i in g[link_b]:
    if is_reciprocal(g,link_a,i,k-1):
        return True

However, you may notice that you now have two nearly-identical loops in a row. If you change your recursive base case to handle the i == link_a case for you (which is trivial: instead of returning False if k == -1, just return link_a == link_b if k == 0), then you can remove the first loop and only have the second one.

Upvotes: 1

Related Questions