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

Question

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

正如您所希望看到的，传递给每个递归级别的唯一参数是“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;}
    }

Answer 1

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

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

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.
    }
}