Adding recursively for installation

I'm trying to wrap my head around recursive functions with this function def friends(self, name, degree):

. The purpose of this is to bring back a set of all friends to a certain extent (for an address book). This is the last part of a larger class called class SocialAddressBook:

. The "degree" in this class allows the user to "query" the friends of friends: the first degree is a direct friend, degree 2 is each other, and so on. The code I have is

def friends(self, name, degree):
    fs = set()
    if degree == 0:
        return set()
    if degree == 1:


as far as I know about it. also another context:

Transitive Friendship:

Fred β†’ Barb β†’ Jane β†’ Emma β†’ Lisa
Fred β†’ Sue
              Jane β†’ Mary


and so my tests are: a.friends('Fred', 1) == {'Barb', 'Sue'}

a.friends('Fred', 2) == {'Barb', 'Jane', 'Sue'}

a.friends('Fred', 3) == {'Mary', 'Barb', 'Jane', 'Sue', 'Emma'}

a.friends('Fred', 4) == {'Barb', 'Emma', 'Mary', 'Lisa', 'Sue', 'Jane'}

it only goes up to degree 4. SO if I even do it recursively or just by hand, so how do I know the degree to which this is happening? ...

If someone can point me in the right direction on how to end this recursively, that would be awesome, thanks!


source to share

2 answers

I would say to do it iteratively: just add friends to the current list n , where n is an input parameter.

fs = set(self)
for i in range (n):
    wider = set()
    for chum in fs.copy():
        for new_chum in chum.friend_list:
            fs += new_chum


At each level, create a wider set of friends from the current set. After you go through all of this, add them to your friend set. Repeat N times.



The best way to do this is iterative.

def get_friends_iteratively(self, name, degree)
    if degree < 0:
        raise ValueError('degree should be an int >= 0')
    if degree == 0:
        return set() # no friends of degree 0!
    friends = self.friends
    for _ in range(degree):
        new_friends = set()
        # it is important not to change a set while we iterate through it.
        # thus, we change new_friends, then update friends when we are done.
        for other_person in self.friends:
            new_friends |= other_person.friends
        friends |= new_friends
    return friends

    # In python, the |= ('in-place or') operator updates a set with
    # the union of itself and another set.




All Articles