6
\$\begingroup\$

I have several situations in which I need to write a recursive function that does things. I'm asking about one special pattern that I use in recursive methods from time to time.
But first an example, so that you know what I'm talking about.

Example

Assume the following C# code:

class Item
{
    public int Id { get; set; }
    public int ParentId { get; set; }
    public string Name { get; set; }
}

void Main()
{
    var items = new List<Item>
    {
        new Item{Id = 1, ParentId = 0, Name = "Root"},
        new Item{Id = 2, ParentId = 1, Name = "Sub1"},
        new Item{Id = 3, ParentId = 2, Name = "Sub2"},
        new Item{Id = 4, ParentId = 2, Name = "Sub3"},
        new Item{Id = 5, ParentId = 2, Name = "Sub4"},
        new Item{Id = 6, ParentId = 4, Name = "Sub5"}
    };

    Console.WriteLine(GetPath(items, items[5]));
}

string GetPath(List<Item> list, Item current, bool inRecursion = false) 
{
    if (current == null)
    {
        return "";
    }

    var res = GetPath(list, list.FirstOrDefault(m => m.Id == current.ParentId), true) + "/" + current.Name;

    if (!inRecursion) 
    {
        res = res.TrimStart('/');
    }

    return res;
}

Explanation

The GetPath method tries to construct a path from one item down to a root item.
It gets a list of all items (list), where each item has an Id, a ParentId and a Name. As second parameter, it takes an item to start with (current).
When called, it calls itself, but with the parent item as current item.
Finally, when an item has no parent, it returns an empty string. The return values from the recursive calls are then appended to the current item's name.

(It's always a little bit hard to explain recursion, I hope it's understandable...)

So, the code above gives me Root/Sub1/Sub3/Sub5 as result.

Question

As you see, the method has a third parameter (inRecursion), which indicates whether the method is in recursion, or not. I use it, to remove the leading / in the path.

I see myself using a boolean flag like this in recursive methods from time to time, but I wonder if this is the way to go, or if there is a better way to solve the problem of indicating the first call, where the method hasn't called itself. Using a flag like this seems somehow dirty to me.

So, is this considered bad practice, or am I all fine with using a flag like this?

\$\endgroup\$
8
\$\begingroup\$

As you see, the method has a third parameter (inRecursion), which indicates whether the method is in recursion, or not. I use it, to remove the leading / in the path.

You need this flag because your function is doing to much. It violates the S (Single responsibility principle) in SOLID. It's not only resolving the elements but it's building the final result at the same time. The method should actually only return a List<string> with all the names (or other itmes) it found so that you can do what ever you need to do with it like:

var names = GetNames(...);
var path = string.Join("/", names);

It doesn't matter if you use recursion or a stack or any other method. The most important part is that it should only do one thing: return a collection of items.

What if you wanted to use a different delimiter such as \ or .? You'd need a new parameter for it. However, if you only have a list of names it's much easier to change it and build a different path because this is another responsibility.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.