Recursion with IEnumerable<T>

October 02, 2021

A recursion is used mostly in a tree/graph search. Let’s look at the simple binary tree:

Find all nodes that reaches x in the above code would be

a -> 2 -> x

If we write code that returns an array, we would write.

public List<string> GetPathTo(Tree tree, string target)
{
  // exit condition
  if (tree == null)
  {
    return null;
  }

  if (tree.Value == target)
  {
    return new List<string> { tree.Value }
  }

  foreach (var tree in new [] { tree.Left, tree.Right })
  {
    var path = GetPathTo(tree.Left, target);
    if (path != null) {
      path.Add(tree.Value)
      return path;
    }
  }
}

// calling the function
Tree tree;
// ... initialize the tree
Console.WriteLine(string.Join(" -> ", GetPathTo(tree, "x").Reverse())); // we added value to the end, so we want to reverse it

What if we want to get all the paths?

public List<List<string>> GetPathTo(Tree tree, string target)
{
  // ... we would add list to list
}

We would have to wait until all search is complete. What if we use IEnumerable we can display as we find them? Or take first few paths rather than the whole?

With coroutine, searching a tree/graph structure is more fun!

private IEnumerable<IEnumerable<T>> GetDfsPathTo(Tree<T> tree, T value)
{
    if (tree == null)
    {
        yield break;
    }
    else if (tree.Value.Equals(value))
    {
        yield return Enumerable.Repeat(tree.Value, 1);
    }

    foreach (var leaf in tree)
    {
        foreach (var path in GetDfsPathTo(leaf, value))
        {
            yield return Enumerable.Repeat(tree.Value, 1).Concat(path);
        }
    }
}

This also allows taking the first value only and stop the process. There’s no reverse needed as we are just appending to the first as well.

Test code can be found at Codyssey repository.