How to deal with deep recursion when working with ArrayLists?
So today I ran into a problem and now it is evening time and all I have done successfully is the source of the problem.
I have a bunch of nodes that make up a shape. These nodes can also have node-child children (think shoulder -> elbow -> arm). A possible scenario for this shape is that one of these nodes could bind many, many generations of child nodes to it (as shown in the figure).
The problem I am facing is that if I run a typical recursive function like updatePosition () when the root node is moved, this function iterates over its row of children and I end up with a StackOverflowError.
The problem I have is I don't know how to get around this limitation. I understand that I have to abandon this recursive method, but how? I would really appreciate some input / advice to point me in the right direction.
Also note, this issue occurs on Android devices, I guess it leaves me with a relatively lower stack limit than a typical desktop JVM.
Edit: As per dangVarmit's solution of using a hand-crafted Stack, this is what I came up with. I haven't been able to test this code yet, but it looks like it will work.
OLD CODE
void validatePosition()
{
if (_positionIsDirty == true)
updatePosition();
}
void updatePosition()
{
_positionIsDirty = false;
// etc...
for (int i = _childrenNodes.size() - 1; i >= 0; --i) // This recursive part caused the StackOverflowError
_childrenNodes.get(i).updatePosition();
}
NEW CODE
void validatePosition()
{
if (_positionIsDirty == true)
{
// Create a Stack and add this Node to it.
Stack stack = new Stack();
stack.push(this);
while (stack.empty() == false)
{
// Pop top-most Node in Stack.
Node node = stack.pop();
// Update it and push its children onto the Stack.
node.updatePosition();
for (int i = node._childrenNodes.size() - 1; i >= 0; --i)
stack.push(node._childrenNodes[i]);
}
}
}
void updatePosition()
{
_positionIsDirty = false;
// etc...
}
source to share
Create a stack or ArrayList of nodes. push the root object onto the stack and run a while loop (not empty for the stack)
the body of the loop runs at the top of the node of the stack. Anytime you step into a function, you will now push a new node onto the stack and then use continue to start a loop at the new top level node.
When a recursive function is executed on a specific node, it pops the node off the stack and causes the loop to continue to start.
Your loop should take into account the fact that it can be called multiple times on the same node so that you can manipulate the state a little. In a recursive function, you return to the parent caller at the same place in the function with the same state (local variables, etc.). You are losing it, so you need to manage this statement. In the left, right child word node, you will need to remember that you checked and processed the left node so that you can skip that on the second pass and check / process the right node this time (or put the stack and continue if you did both nodes)
source to share