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?