时间戳

首页 > 解决方案 > 您如何将其转换为迭代函数而不是使用嵌套循环进行递归？

c# - 您如何将其转换为迭代函数而不是使用嵌套循环进行递归？

问题描述

以下函数导致数百个级别的递归。我想知道是否有人对如何将其切换为循环功能提出建议。我相信在这种情况下执行顺序确实很重要，但我可能需要做更多的调查。我希望我可以直接将它转换为迭代函数而不是递归。

正如您所希望看到的，传递给每个递归级别的唯一参数是“after”。所以递归函数调用本身相对简单，但是围绕调用的循环让我很反感。

我考虑过排队，但“改变”的条件似乎意味着深度优先检查。在将其添加到队列之前，我必须执行部分移位操作，但在当前代码中，下一级递归将立即开始，所以我不能只建立一个项目队列来处理和执行他们按顺序。

我考虑过一个堆栈，但我不确定如何实现它来替换递归。

我决定简化代码，因为它可能有点令人困惑。这是一个骨架（如果您初始化变量，您实际上可以运行它！）这可能更像是“伪”

    private void DataChangedRecursive(LinkedNode node)
    {
        InitializeVariables();
        try
        {
            foreach (LinkedNode after in node.After)
            {
                var afterDetails = after.Before;
                bool changed = CheckData(afterDetails);

                if (changed)
                {
                    DataChangedRecursive(afterDetails);
                }
            }
        }
        catch 
        {
            // Assume relavant error handling at this level in the stack.  This probably isn't important to maintain, but it'd be interested if we could.
            throw;  
        }
    }
    
    public object InitializeVariables()
    {
        // Assume relavant work happens here.
        return new object();
    }
    
    public bool CheckData(LinkedNode dr)
    {
        // Logic is that something changes, so it needs to save.  This does a bunch of comparisons on the current item.
        return dr.DataChanged;
    }
    
    public class LinkedNode
    {
        public LinkedNode Before {get;set;}
        public bool DataChanged {get;set;}
        public List<LinkedNode> After {get;set;}
    }

标签： c#recursioniteration

解决方案

终于想通了，顿悟了。事实证明，处理递归和循环的最简单方法是利用 IEnumerator。它要求您手动处理迭代（没有 for 循环），但递归和循环的顺序将是相同的。

我将函数分为两部分，入口函数和与“递归”一起进行迭代的函数。从本质上讲，这将保证所有子节点首先完全完成，就像递归一样，并返回父节点中正确的迭代点。理论上，这应该适用于任何内部带有循环的递归函数。

private void DataChangedRecursive(LinkedNode node)
{
    try
    {
        DataChanged(node);
    }
    catch 
    {
        throw;  
    }
}

private void DataChanged(LinkedNode node)
{
    var state = new Stack<IEnumerator<LinkedNode>>();
    state.Push(node.After.GetEnumerator());

    while (state.Count > 0)
    {
        InitializeVariables();
    
        while (state.Peek().MoveNext())
        {
            ItemWithPredPostcessor after = state.Peek().Current;
            ItemWithPredPostcessor afterDetails = after.Before;
            bool dataChanged = StartShift(afterDetails);

            if (dataChanged)
            {
                Save(afterDetails);
                state.Push(afterDetails.After.GetEnumerator());
            }
        }
        state.Pop(); // Remove current from list, as we've completed.
    }
}

推荐阅读