How to convert recursive procedure with side effects on ref param to recursive function returning a list?

Question

It seems every time I go to write a recursive function I end up making it return void and using a ref parameter.

I'd much rather be able to write a function that just returns a result list.

Apologies if the answer is very simple - for some reason it elludes me.

Here's the code I have now:

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;
        }
    }
}

I'd like to know if it can be rewritten to the prototype:

public static List<XDocument> GetResources(string startURL)

it's good for implying the side effect of the procedure though no? — Aaron Anodide, Aug 15 '11 at 22:05
A proper comment is sufficient. You're not actually *using* the fact that the parameter is `ref`, mostly because there's no reason to do so. — dlev, Aug 15 '11 at 22:06
The code is not complete, please add the initializations needed. resourceList and GetXml. Also in the situation you are traversing a tree structure of unknown shape, a recursive function is a good natural way to do that. — MrFox, Aug 15 '11 at 22:12

score 3 · Accepted Answer · answered Aug 15 '11 at 22:05

I guess something like:

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;
}

that's the way my brain was thinking of but I couldn't think of, thanks. — Aaron Anodide, Aug 15 '11 at 22:09

Jon Skeet · Answer 2 · 2011-08-15T22:11:58.233

For one thing, there's absolutely no point in that being a ref parameter in the first place. It's quite possible that you don't understand ref parameters - see my article on this topic.

As this is naturally recursive, I'd probably write it like this:

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);
    }
}

You can keep it in a recursive fashion and create a new list at every level, but it feels a little ugly to me. The above gives you the public API you want, but without allocating collections left, right and centre.

Now you could write it in a non-recursive fashion, basically by creating a queue of URLs to work through:

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;
}

It's too late in the day for me to work out whether this gives the results in the same order - I suspect it doesn't - but hopefully that's not important.

(You don't really have a type called resourceList do you? ResourceList, please!)

+♡x100 for being polite and without betraying a bit of arrogance as you stated your style preference: no absolutes given, phrased as request, and this despite whatever level of certainty you may have that your preference is "The One True Style". most excellent. [And, as founder of the 'Unofficial Jon Skeet Beat Me to it Fan Club', I feel especially happy it was you. No, seriously, 'cause I'm kinda running low on the "+♡'s" for the week, and who knows when you might need those things, right?] Oh, and also +1 for the wikked great answer for Gabriel. No "+♡'s" for that though, just a vote. ;) — shelleybutterfly, Aug 15 '11 at 22:41
@shelleybutterfly: Oh there's definitely no "one true style" in this case. On a different day I might have chosen the accepted approach :) — Jon Skeet, Aug 15 '11 at 22:52
@Jon :) well, I was referring specifically to the coding style comment: "You don't really have a type called resourceList do you? ResourceList, please!" but as always, you are very down-to-earth. not surprised, but inspired. I had been finding myself bothered by some "The One True Style" believers recently. so, it's appreciated. thank you. — shelleybutterfly, Aug 15 '11 at 23:26
@Jon, why do you dislike allocating a new list on each level? Is it a matter of principle, or are there performance considerations? — Konrad Morawski, Aug 16 '11 at 11:34
@Morawski: Well there's obviously the performance consideration, but that would be micro-optimizing. It just feels like it's expressing the wrong thing, somehow. We know we're trying to create a single list for the whole tree, so let's represent that... — Jon Skeet, Aug 16 '11 at 12:20

score 2 · Answer 3 · answered Aug 15 '11 at 22:05

The code looks fine as is (minus the unnecessary ref on the parameter.) One option is to wrap the recursive method in a non-recursive companion:

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

    return retDocs;
}

score 1 · Answer 4 · answered Aug 16 '11 at 00:12

Well, I have a pattern I have used on occasion, and I wanted to show it as an option. However, my brain was a bit ticked off when I tried to tackle it as written, so instead we came to an agreement (my brain and I) that we would just figure out a simple version to show you.

It may not even be quite applicable to your specific question, but it's one way I have used in the past when I wanted things done in a non-mutable fashion, which seemed to be what you were looking for.

    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();
    }

So, there is the pattern, for what it's worth. It's not XML, it doesn't branch, but it's a succinct example of when a non-mutating recursion is easy to implement and is more understandable (to me) than trying to implement the same thing by, say, mutating a StringBuilder.

Really, your particular example seems to flow better (to me) as the two-step solution with a single List return value created at the beginning. :)

I appreciate your addition to the answers - these all give me good ideas that I would not have come up with myself. — Aaron Anodide, Aug 16 '11 at 01:46

How to convert recursive procedure with side effects on ref param to recursive function returning a list?

4 Answers4

Linked