如何将对 ref 参数有副作用的递归过程转换为返回列表的递归函数？

Question

似乎每次我去编写递归函数时，我最终都会使其返回 void 并使用 ref 参数。

我更愿意编写一个只返回结果列表的函数。

如果答案很简单，我很抱歉 - 由于某种原因它让我困惑。

这是我现在的代码：

public static void GetResrouces(string startURL, ref List<XDocument> result)
{
    var doc = XDocument.Parse(GetXml(startURL)); // GetXml ommitted - returns xml string
    var xs = new XmlSerializer(typeof(resourceList));
    var rdr = doc.CreateReader();
    if (xs.CanDeserialize(rdr))
    {
        var rl = (resourceList)xs.Deserialize(doc.CreateReader());

        foreach (var item in rl.resourceURL)
        {
            GetResrouces(startURL + item.location, ref result);
        }
    }
    else
    {
        result.Add(doc);
    }
}

public partial class resourceList
{

    private resourceListResourceURL[] resourceURLField;

    private string locationField;

    /// <remarks/>
    [System.Xml.Serialization.XmlElementAttribute("resourceURL")]
    public resourceListResourceURL[] resourceURL
    {
        get
        {
            return this.resourceURLField;
        }
        set
        {
            this.resourceURLField = value;
        }
    }

    /// <remarks/>
    [System.Xml.Serialization.XmlAttributeAttribute(DataType = "anyURI")]
    public string location
    {
        get
        {
            return this.locationField;
        }
        set
        {
            this.locationField = value;
        }
    }
}

我想知道是否可以将其重写为原型：

public static List<XDocument> GetResources(string startURL)

Answer 1

我猜是这样的：

public static List<XDocument> GetResources(string startURL)
{
    var result = new List<XDocument>();
    var doc = XDocument.Parse(GetXml(startURL));
    var xs = new XmlSerializer(typeof(resourceList));
    var rdr = doc.CreateReader();
    if (xs.CanDeserialize(rdr))
    {
        var rl = (resourceList)xs.Deserialize(doc.CreateReader());

        foreach (var item in rl.resourceURL)
        {
            result.AddRange(GetResources(startURL + item.location));
        }
    }
    else
    {
        result.Add(doc);
    }
    return result;
}

Answer 2

代码看起来很好（减去参数上不必要的 ref）。一种选择是将递归方法包装在非递归同伴中：

public static List<XDocument> GetResources(string startURL)
{
    List<XDocument> retDocs = new List<XDocument>();
    GetResources(startURL, retDocs);

    return retDocs;
}

Answer 3

一方面，作为 ref 参数一开始就没有任何意义。您很可能不理解 ref 参数 - 请参阅我的文章关于这个主题。

由于这是自然递归的，我可能会这样写：

public static List<XDocument> GetResources(string startURL)
{
    List<XDocument> ret = new List<XDocument>();
    GetResourcesRecursive(startURL, ret);
    return ret;
}

private static void GetResourcesRecursive(string startURL,
                                          List<XDocument> result)
{
    var doc = XDocument.Parse(GetXml(startURL));
    var xs = new XmlSerializer(typeof(resourceList));
    var rdr = doc.CreateReader();
    if (xs.CanDeserialize(rdr))
    {
        var rl = (resourceList)xs.Deserialize(doc.CreateReader());

        foreach (var item in rl.resourceURL)
        {
            GetResourcesRecursive(startURL + item.location, ref result);
        }
    }
    else
    {
        result.Add(doc);
    }
}

您可以以递归方式保持它并在每个级别创建一个新列表，但对我来说有点难看。上面为您提供了您想要的 public API，但没有向左、右和中心分配集合。

现在您可以以非递归方式编写它，基本上是通过创建一个要处理的 URL 队列来完成：

public static List<XDocument> GetResources(string startURL)
{
    List<XDocument> ret = new List<XDocument>();
    Queue<string> urls = new Queue<string>();
    urls.Enqueue(startUrl);
    while (urls.Count > 0)
    {
        string url = urls.Dequeue();
        var doc = XDocument.Parse(GetXml(url));
        var xs = new XmlSerializer(typeof(resourceList));
        var rdr = doc.CreateReader();
        if (xs.CanDeserialize(rdr))
        {
            var rl = (resourceList) xs.Deserialize(doc.CreateReader());

           foreach (var item in rl.resourceURL)
           {
               queue.Enqueue(url + item.location);
           }
        }
        else
        {
            ret.Add(doc);
        }  
    }
    return ret;
}

对于我来说，现在已经太晚了，无法确定这是否以相同的顺序给出结果- 我怀疑不是 - 但希望这并不重要。

（您真的没有一个名为resourceList的类型吗？ResourceList，拜托！）

Answer 4

嗯，我有一个偶尔使用过的模式，我想将它作为一个选项来展示。然而，当我试图按照书面方式解决它时，我的大脑有点不舒服，所以我们达成了一项协议（我的大脑和我），我们只会找出一个简单的版本来向您展示。

它甚至可能不太适用于您的具体问题，但这是我过去使用的一种方式，当我希望以不可变的方式完成事情时，这似乎正是您所寻找的。

    public string IntCSVReverse(List<int> IntList)
    {
        return IntCSVReverse_recurse(IntList, 0);
    }

    private string IntCSVReverse_recurse(List<int> IntList, int Index)
    {
        if (Index == (IntList.Count - 1))
            return IntList[Index].ToString();
        else
            return
                IntCSVReverse_recurse(IntList, Index + 1)
                + "," + IntList[Index].ToString();
    }

所以，这个模式是有其价值的。它不是 XML，它没有分支，但它是一个简洁的示例，说明非变异递归很容易实现，并且（对我来说）比尝试通过变异 来实现相同的事情更容易理解字符串生成器。

确实，您的特定示例似乎（对我来说）更好地作为两步解决方案，在开始时创建了一个列表返回值。 :)