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!
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.