c# - C#中的递归函数

Question

我有一个对象，我们称它为“朋友”。这个对象有方法“GetFriendsOfFriend”，它返回一个List<Friend>.

假设用户输入 5，则所有 Friends 朋友和 Friends Friends 朋友（你明白了）的级别下降到 5 级（最高可达 20 级）。

这可能是很多计算，所以我不知道递归是否是最好的解决方案。

有没有人有一个聪明的想法1.如何最好地完成这个递归函数？2.如何做到不递归。

谢谢！

Answer 1

虽然在没有递归的情况下当然可以做到这一点，但我看不出你正在尝试做的事情有什么特别的问题。为了防止事情变得疯狂，设置一个最大值来防止你的程序死掉可能是有意义的。

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用来检查重复项。

Answer 2

这是此代码的非递归版本：

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 并且不添加要处理的成员多次来避免无限循环。

它使用队列访问朋友，这种方式称为广度优先搜索。如果我们使用堆栈而不是队列，它会变成深度优先搜索，并且行为与递归方法（使用隐式堆栈 - 调用堆栈）几乎相同。