Recursive function with big dictionary caused stack overflow problem

Question

I have this recursive function that generates a tree, when the dictionary is smaller, it works fine, but when the dictionary gets bigger, it throws me a stack overflow exception. I know that I shouldn't be increasing the stack to solve the problem. Is there any idea to optimize this recursive function?

public async static Task<SchemaNodeForGetDto> schemaDecompositionGenerator ( SchemaNodeForGetDto startNode, Dictionary<string, OntologyObjectAttrDictionaryDto> objectsLibrary, Dictionary<string, OntologyObjectPartsDto> objectDecompo, ILogger _logger )
    {
        //get child of the start node
        IEnumerable<OntologyObjectPartDto> decompoParts = objectDecompo[startNode.uri].parts;
        IEnumerable<SchemaNodeForGetDto> children = await Task.WhenAll(decompoParts.Select(async x => {
            SchemaNodeForGetDto node = new SchemaNodeForGetDto();
            node.uri = x.partIri;
            node.name = objectsLibrary.ContainsKey(x.partIri) ? objectsLibrary[x.partIri].en : "";
            node.constraint = x.constraint;
            node.attributes = objectsLibrary.ContainsKey(x.partIri) ? objectsLibrary[x.partIri].attributes : Enumerable.Empty<string>();

            //recursive the tree generation
            if (objectDecompo.ContainsKey(node.uri)) {
                await schemaDecompositionGenerator(node, objectsLibrary, objectDecompo, _logger);
            }

            // return the child node
            return node;
        }));

        startNode.children = children;

        return startNode;

    }

Yes, stop using recursion and rewrite the method so that it uses iteration instead. — aybe, Dec 12 '22 at 04:47
But I don't know how many layers the tree would be, hence why I am using the recursive function, i don't know how to use iteration in this case to construct the tree — amy cai, Dec 12 '22 at 08:12
Related: [Way to go from recursion to iteration](https://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration). — Theodor Zoulias, Dec 13 '22 at 21:12

score 3 · Answer 1 · answered Dec 12 '22 at 13:29

3

i don't know how to use iteration in this case to construct the tree

Recursive functions can be transformed to iterative functions by maintaining your own stack (or queue) explicitly.

Alternatively, if you want a quick solution, you can add await Task.Yield(); at the beginning of your method.

answered Dec 12 '22 at 13:29

Stephen Cleary

437,863
77
675
810

I am trying to use a queue combined with the while loop, but can't get around creating this tree, do you have an example for this use case? – amy cai Dec 13 '22 at 10:12
No. For a tree-like structure you'd probably need to keep the parent as well as the child node in the queue. It should work well if you can append to the children collection instead of overwriting it. – Stephen Cleary Dec 13 '22 at 10:46

Recursive function with big dictionary caused stack overflow problem

1 Answers1