再帰的に設定を追加する

Question

私はこの1つの関数def friends(self, name, degree):を使用して再帰関数を頭に入れようとしています。この1つの目的は、すべての友人の集合を特定の程度まで（アドレス帳のために）返すことです。それはclass SocialAddressBook:と呼ばれる大きなクラスの最後の部分です。このクラスの「程度」は、ユーザーが友人の友人に「質問」することを可能にします。度1は直接の友人であり、次数2は友人の友人であり、以下同様です。

推移友情：：私が持っているコードはまた、いくつかのより多くのコンテキストこの上の私の知識が行く限りで

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

.... ある

Fred → Barb → Jane → Emma → Lisa 
Fred → Sue 
       Jane → Mary 

と私のテストは：a.friends('Fred', 1) == {'Barb', 'Sue'}

です。

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

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

それだけで私はそれがに上がる度を知っているので、SO、私も再帰的にまたはちょうどこれを手動で行う必要がある度4 に上がりますか？ 。

誰かがこれを再帰的に完了する方法について正しい方向で私を指すことができれば、それはすばらしいでしょう、ありがとう！

Answer 1

私は繰り返しこれを行うには言う：ただ、それは現在のリストにn個は、入力パラメータであるのn回、友人を追加します。

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 

各レベルで、現在のセットの友人からより広いセットを作成します。一度それらのすべてを通過したら、それらを友人セットに加えてください。繰り返すN回。

Answer 2

これを繰り返し行うのが最善です。

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.