c# - 我是否需要递归函数来遍历 Dictionary 的 Dictionary？

Question

而且可能有很多层次，谁知道它能深入到什么程度呢!对于这个特定问题，我们还假设另一个字典的字符串将是“字典”，而我想要访问/修改的值将是“数据”。

Answer 1

Will I need a recursive function to iterate through a Dictionary<String, Object> of Dictionary<String, Object>s?

不。任何递归算法都可以重写为使用显式堆栈而不是调用堆栈。

Is it easier to use recursion to do so?

也许。但是，如果结构嵌套非常深(或包含循环)，您可能会遇到堆栈溢出异常的风险。

非递归实现并不是特别难实现。这将需要您维护一个列表(堆栈或队列，具体取决于您要访问子项的顺序)，以跟踪尚未访问的子词典。

原型(prototype)(非递归)实现类似于:

public IEnumerable<string> GetAllKeys( Dictionary<string,object> dictionary )
{
    var stackDictionariesToVisit = new Stack<Dictionary<string,object>>();

    stackDictionariesToVisit.Push( dictionary );

    // keep visiting iterating until the stack of dictionaries to visit is empty
    while( stackDictionariesToVisit.Count > 0 )
    {
        var nextDictionary = stackDictionariesToVisit.Pop();
        foreach( var keyValuePair in nextDictionary )
        {
            if( keyValuePair.Value is Dictionary<string,object> )
            {
                stackDictionariesToVisit.Push( 
                     keyValuePair.Value as Dictionary<string,object> );
            }
            else
            {
                yield return keyValuePair.Key;
            }
        }
    }
}

上面的实现没有错误检查，也没有检查循环，但它用显式堆栈代替了递归。

是否使用递归(或不使用)来访问分层数据结构的选择应该取决于对存储数据类型的理解，而不是哪种方法更容易。如果您有深度嵌套的结构，你最好不使用递归，因为你无法控制可用的堆栈空间。另一方面，如果您确信数据永远不会嵌套超过几层，则递归实现可能(稍微)更容易理解和维护。