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!

+3

source to share

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.

+2

source

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

```
+2

source

All Articles