1
$\begingroup$

I'm struggling on this one. I have a Binary Decision Diagram, which is pretty much tree-like. Each node has a hi and lo node. I need to recurse into the tree, and if some conditions are the case replace the node with a new node. Nodes are immutable. So when I encounter something I have to change, I have to return the new version of the node all the way up. Ultimately the root changes. Specifically I'm trying to implement the RESTRICT algorithm for ROBDDs.

And I have! This works fine (C#, sorry?)

        Node Restrict(Node node, Func<Variable, bool?> npoint)
        {
            if (node == context.Term0 || node == context.Term1)
                return node;

            // value has been restricted, replace with true or false path
            if (npoint(node.Variable) is bool value)
                return Restrict(value ? node.Hi : node.Lo, npoint);

            var lo = Restrict(node.Lo, npoint);
            var hi = Restrict(node.Hi, npoint);
            return new Node(node.Variable, lo, hi);
        }

However, my diagram is rather huge. And I'm running out of stack space.

So, I'm trying to come up with a way to do this without recursion. I've tried a few things but haven't come up with anything that works. As I start to expand it out, it gets pretty complicated and I start losing track of stuff.

Can somebody point me to some resource on this?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ StackOverflow.com is the site in this network for getting help with specific code. Answers here should really stick to the principles of turning recursive code into iterative code with a stack of continuations. I suggest you press the "flag" link and make a custom flag to request migration. $\endgroup$ – Peter Taylor Aug 2 '19 at 6:46