c# - Convert method from recursive to iterative

Question

I have the following method that is recursive and works pretty well but potentially can cause an StackOverflow exception, so I thought to convert this method to iterative one. However I struggled a lot and still don't have idea how to do it properly.

Example input

My recusrive method

    private IDictionary<string, object> AsDtoObjRecursive(IDictionary<string, object> dict)
    {
        dict = new Dictionary<string, object>(dict);
        var temp = new Dictionary<string, object>(dict);
        foreach (var key in temp.Keys)
        {
            object value = temp[key];
            if (value == null) continue;
            switch (value)
            {
                case ICollection collection:
                {
                    foreach (var dynamicValue in collection)
                    {
                        if (dynamicValue is ExpandoObject o)
                        {
                            dict[key] = AsDtoObjRecursive(o);
                        }
                        else
                        {
                            dict[key] = (object) dynamicValue;
                        }
                    }

                    break;
                }
                case ExpandoObject o:
                    dict[key] = AsDtoObjRecursive(o);
                    break;
                default:
                    dict[key] = (object) value;
                    break;
            }
        }

        return dict;
    }

The propert output - recursive:

My approach to iterative one, but it is really really dumb and is safe only for input example above...

   private IDictionary<string, dynamic> AsDtoObjIterative(IDictionary<string, dynamic> dict)
    {
        var stack = new Stack<(string key, IDictionary<string, object>)>();
        stack.Push((null, new Dictionary<string, object>()));
        dict = new Dictionary<string, object>(dict);
        do
        {
            var (keyStack, dictionary) = stack.Pop();
            dictionary = new Dictionary<string, object>(dictionary);

            IDictionary<string, object> temp = dictionary.Any()
                ? new Dictionary<string, object>(dictionary)
                : new Dictionary<string, object>(dict);

            foreach (var key in temp.Keys)
            {
                var value = temp[key];
                if (value == null && _options.IgnoreNullValues) continue;
                switch (value)
                {
                    case ICollection collection:
                    {
                        foreach (var dynamicValue in collection)
                        {
                            if (dynamicValue is ExpandoObject o)
                            {
                                if (keyStack != null)
                                    dict[keyStack] = dictionary;

                                stack.Push((key, o));
                                temp = o;
                            }
                            else
                            {
                                dict[key] = (object) dynamicValue;
                            }
                        }

                        break;
                    }
                    case ExpandoObject o:

                        if (keyStack != null)
                            dict[keyStack] = dictionary;
                        stack.Push((key, o));
                        temp = o;

                        break;
                    default:
                        if (keyStack != null)
                        {
                            if (dict.ContainsKey(keyStack))
                            {
                                dict[keyStack] = (object) value;
                            }
                            else
                            {
                                var o = dict[dict.Keys.Last()];
                                var o1 = o[keyStack];
                                (o1 as IDictionary<string, object>)[key] = (object) value;
                            }
                        }
                        else
                        {
                            dict[key] = (object) value;
                        }

                        break;
                }
            }
        } while (stack.Count != 0);

        return dict;
    }

And still I have the wrong output cause I can't handle properly the tree data structure.

Wrong output -iterative:

PS. Sorry for putting images, not json but if I convert to json, it's loses whole sense.

question from:https://stackoverflow.com/questions/66065359/convert-method-from-recursive-to-iterative

Answer 1

Waitting for answers