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中的递归函数＃

回答

相关问题