懒惰递归函数的非递归等价

本文关键字：递归 递归函数 | 更新日期: 2023-09-27 18:22:14

考虑以下代码在Rose Tree上实现深度优先搜索：

public class RoseTree<T>
{
    public T Value;
    public IEnumerable<Lazy<RoseTree<T>> Children;
    public IEnumerable<T> Flatten()
    {
        yield return Value;
        foreach (var childValue in Children.SelectMany(t => t.Value.Flatten()))
            yield return childValue;
    }
}

我一直在努力想出一个等价的非递归等价物。特别是，尽管很容易得到严格的非递归、拟等价函数，例如：

public IEnumerable<T> FlattenIteratively()
{
    var roseTreeQueue = new Stack<RoseTree<T>>();
    var values = new Queue<T>();
    roseTreeQueue.Push(this);
    while (roseTreeQueue.Any())
    {
        var top = roseTreeQueue.Pop();
        values.Enqueue(top.Value);
        foreach (var child in top.Children.Reverse())
            roseTreeQueue.Push(child.Value);
    }
    return values;
}

虽然对于具有定义值的有限树，这会产生与Flatten相同的结果，但对于无限树或具有未定义值的树，这将失败。有没有人看到一种写非递归方法的方法来遍历这个结构，它具有与递归方法相同的特性。

注意：考虑到C#对yield return函数的重写，调用第一个方法recursive有点误导。如果有人有更精确的术语，我很乐意拥有。

懒惰递归函数的非递归等价

一个通用的惰性迭代树遍历函数，取自How to flatten tree via LINQ？

public static class TreeHelper
{
    public static IEnumerable<T> Expand<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)
    {
        var stack = new Stack<IEnumerator<T>>();
        var e = source.GetEnumerator();
        try
        {
            while (true)
            {
                while (e.MoveNext())
                {
                    var item = e.Current;
                    yield return item;
                    var elements = elementSelector(item);
                    if (elements == null) continue;
                    stack.Push(e);
                    e = elements.GetEnumerator();
                }
                if (stack.Count == 0) break;
                e.Dispose();
                e = stack.Pop();
            }
        }
        finally
        {
            e.Dispose();
            while (stack.Count != 0) stack.Pop().Dispose();
        }
    }
}

在您的情况下，它可以按以下使用

public class RoseTree<T>
{
    public T Value;
    public IEnumerable<Lazy<RoseTree<T>>> Children;
    public IEnumerable<T> Flatten()
    {
        return Enumerable.Repeat(this, 1)
            .Expand(item => item.Children != null ? item.Children.Select(c => c.Value) : null)
            .Select(item => item.Value);
    }
}

我们可以通过将FlattenIterative方法显式转换为IEnumerator<T>来解决此问题。我们定义：

public class RoseTreeEnumerator<T> : IEnumerator<T>, IEnumerable<T>
{
    public RoseTree<T> OriginalTree { get; private set; }
    private Stack<Lazy<RoseTree<T>>> TreeQueue { get; set; }
    private RoseTree<T> CurrentRoseTree { get; set; }

    public RoseTreeEnumerator(RoseTree<T> tree)
    {
        OriginalTree = tree;
        TreeQueue = new Stack<Lazy<RoseTree<T>>>();
        TreeQueue.Push(new Lazy<RoseTree<T>>(() => tree));
        CurrentRoseTree = null;
    }  
    #region IEnumerator<T> Members
    public T Current
    {
        get { return CurrentRoseTree.Value; }
    }
    public void Dispose()
    {
    }
    #endregion
    #region IEnumerator Members
    object System.Collections.IEnumerator.Current
    {
        get { return Current; }
    }
    public bool MoveNext()
    {
        if (TreeQueue.Any())
        {
            CurrentRoseTree = TreeQueue.Pop().Value;
            foreach (var tree in CurrentRoseTree.Children.Reverse())
            {
                TreeQueue.Push(tree);
            }
            return true;
        }
        else
        {
            return false;
        }
    }
    public void Reset()
    {
        TreeQueue.Clear();
        CurrentRoseTree = null;
        TreeQueue.Push(new Lazy<RoseTree<T>>(() => OriginalTree));
    }
    #endregion
    #region IEnumerable<T> Members
    public IEnumerator<T> GetEnumerator()
    {
        return this;
    }
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return this;
    }
    #endregion
}

然后可以定义

public IEnumerable<T> FlattenPrime()
{
    return new RoseTreeEnumerator<T>(this);
}
相关文章：