C中的遞歸函數＃

我有一個對象，我們稱它爲「朋友」。此對象的方法「GetFriendsOfFriend」，返回List<Friend>。C中的遞歸函數＃

給出用戶輸入的說5，所有朋友朋友和朋友朋友（你得到的點）在5級（這可以是20）。

這可能是很多計算，所以我不知道遞歸是最好的解決方案。

有沒有人有一個聰明的想法 1.如何做到這一點最好的遞歸功能？ 2.如何做到無遞歸。

謝謝！

來源

2012-07-26 Annish

朋友們是如何真正相互關聯的？ – 2012-07-26 14:32:04

沒有這些計算的細節和涉及的數據，這是不可能回答的，除非說迭代和遞歸解決方案几乎肯定是可能的。但任何更具體或明確的要求細節。 – Richard 2012-07-26 14:32:10

還要考慮在共同朋友的情況下會發生什麼。你不想結束無限的遞歸。 – 2012-07-26 14:32:12

雖然無需遞歸就可以做到這一點，但是我並沒有看到您想要做什麼的特定問題。爲了防止事情變得瘋狂，設置最大值以防止程序死亡可能是有意義的。

public class Friend 
{ 
    public static readonly int MaxDepth = 8; // prevent more than 8 recursions 

    private List<Friend> myFriends_ = new List<Friend>(); 

    // private implementation 
    private void InternalFriends(int depth, int currDepth, List<Friend> list) 
    { 
     // Add "us" 
     if(currDepth > 1 && !list.Contains(this)) 
      list.Add(this); 

     if(currDepth <= depth) 
     { 
      foreach(Friend f in myFriends_) 
      { 
       if(!list.Contains(f)) 
        f.InternalFriends(depth, depth + 1, list); // we can all private functions here. 
      } 
     } 
    } // eo InternalFriends 


    public List<Friend> GetFriendsOfFriend(int depth) 
    { 
     List<Friend> ret = new List<Friend>(); 
     InternalFriends(depth < MaxDepth ? depth : MaxDepth, 1, ret); 
     return ret; 
    } // eo getFriendsOfFriend 
} // eo class Friend

編輯：修正了代碼中的一個錯誤，因爲真正的朋友不會被添加，只是「他們」的朋友。只有在深度爲「1」（第一個呼叫）後添加朋友時才需要。我也利用Contains來檢查重複項。

來源

2012-07-26 14:38:47

下面是該代碼的非遞歸版本：

public static void ProcessFriendsOf(string person) { 
    var toVisit = new Queue<string>(); 
    var seen = new HashSet<string>(); 

    toVisit.Enqueue(person); 
    seen.Add(person);   

    while(toVisit.Count > 0) { 
     var current = toVisit.Dequeue();  

     //process this friend in some way 

     foreach(var friend in GetFriendsOfFriend(current)) { 
      if (!seen.Contains(friend)) { 
       toVisit.Enqueue(friend); 
       seen.Add(friend); 
      } 
     } 
    } 
}

它通過保持已經看到所有成員的一個HashSet，並且不添加到被處理多次的成員避免無限循環。

它以一種被稱爲Breadth-first search的方式使用隊列訪問朋友。如果我們使用堆棧而不是隊列，它將變成Depth-first search，並且與遞歸方法（使用隱式堆棧 - 調用堆棧）的行爲幾乎相同。

來源

2012-07-26 15:52:55

C中的遞歸函數＃

回答

相關問題