How to convert a recursive procedure with side effects to ref param for a recursive function that returns a list?

Question

It seems that every time I go to write a recursive function, I end up returning void and using the ref parameter.

I could rather write a function that simply returns a list of results.

I apologize if the answer is very simple - for some reason it covers me.

Here is the code that 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 would like to know if it can be rewritten to the prototype:

 public static List<XDocument> GetResources(string startURL) 

Answer 1

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

Answer 2

Firstly, there is absolutely no sense that this is a ref parameter. It is possible that you do not understand the parameters of ref - see my article on this subject .

Since this is naturally recursive, I would 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 save it in a recursive way and create a new list at each level, but it feels a little ugly for me. The above gives you the public API you want, but without highlighting the collections on the left, right, and center.

Now you can write it in a non-recursive way, 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 a day for me to find out if this gives the results in the same order — I suspect this is not the case — but hopefully this is not important.

(You really don't have type resourceList , you? resourceList , please!)

Answer 3

The code looks great as it is (minus the unnecessary ref parameter). One option is to wrap a 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; } 

Answer 4

Well, I have a sample that I used sometimes, and I wanted to show it as an option. However, my brain responded a bit when I tried to handle it as it is written, so instead we agreed (my brain and I) that we would simply calculate a simple version to show you.

This may not even be entirely applicable to your specific question, but this is one of the ways that I used in the past when I wanted things to be done in an immutable way, 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 a sample for what it stands. This is not XML, it does not branch, but this is a brief example of when non-mutating recursion is easy to implement and more understandable (for me) than trying to implement the same thing, say, using StringBuilder mutation,

Indeed, your specific example seems to work better (for me) as a two-stage solution with a single List return value created at the beginning. :)