Trying to replace a tail recursive call by a loop

Question

On this question there is a recursive function that finds a parent :

public static T FindParent<T>(DependencyObject child) where T : DependencyObject
{
    DependencyObject parentObject = VisualTreeHelper.GetParent(child);
    if (parentObject == null) return null;
    var parent = parentObject as T;
    if (parent != null)
    {
        return parent;
    }
    return FindParent<T>(parentObject);
}

Resharper offers me to convert it to a loop instead of recursion, it does it like that :

public static T FindParent<T>(DependencyObject child) where T : DependencyObject
{
    while (true)
    {
        DependencyObject parentObject = VisualTreeHelper.GetParent(child);
        if (parentObject == null) return null;
        var parent = parentObject as T;
        if (parent != null)
        {
            return parent;
        }
        child = parentObject;
    }
}

---

Now I have a function that collapses expanded groups and all its sub-groups :

Unfortunately Reshaper does not offer me to convert it like the one above :(

private void MenuItemCollapseAll_OnClick(object sender, RoutedEventArgs e)
{
    // ... truncated for brievety
    IEnumerable<CollectionViewGroup> groups = grid.Items.Groups.OfType<CollectionViewGroup>().ToArray();
    CollapseGroups(grid, groups);
}

public void CollapseGroups(DataGridControl grid, IEnumerable<CollectionViewGroup> groups)
{
    foreach (var @group in groups)
    {
        grid.CollapseGroup(group);
        var subGroups = @group.Items.OfType<CollectionViewGroup>().ToArray();
        if (subGroups.Any())
        {
            CollapseGroups(grid, subGroups);
        }
    }
}

I just can't figure out how to convert it in the same way using a while statement, not entirely sure whether it's possible for this very function.

Any ideas ?

Answer 1

It's not tail-recursive. After the recursive call comes another iteration of the foreach loop. But, not all hope is lost.

What you can do to convert it to iteration is make a Stack<Tuple<DataGridControl, IEnumerable<CollectionViewGroup>> and replace the recursive call with pushing a new tuple onto the stack. Then loop until the stack is exhausted.

But first, I notice that the first parameter never changes. So the iterative version doesn't actually need to keep that on the stack:

public void CollapseGroups(DataGridControl grid, IEnumerable<CollectionViewGroup> groups)
{
    var to_process = new Stack<IEnumerable<CollectionViewGroup>>();
    to_process.Push(groups);
    do {
        groups = to_process.Pop();
        foreach (var @group in groups)
        {
            grid.CollapseGroup(@group);
            to_process.Push(@group.Items.OfType<CollectionViewGroup>());
        }
    } while (to_process.Count > 0);
}