That's something that I do on a daily basis -- manipulate binary trees in Netlinx.
I've experimented with recursive functions in Netlinx and have had bad results. I don't think the subject of recursion is discussed in any of the AMX literature or training. I just assumed that it was not supported or "buggy" and moved on.
Actually, I think I remember what I was up to: somebody wanted to know how to calculate a nlog in Netlinx and in response I tried to write a recursive function to calculate the log based on a series expansion. The recursion kept blowing up so I just did it with a loop (as I recall). Looking at it again about a year ago, it seems that there was probably an easier way to do it, but then, something totally unimportant came up and I got distracted. Probably something like calculating the nlog of a negative number.
Try and write a function that prints the nodes in a tree iteratively. The only way to find your way back up the tree is through the call stack, using recursion.
Paul
The non-recursive solution uses an explicit data structure (a stack) of nodes to traverse, rather than keeping that information on the call stack. In pseudo-code, for pre-order traversal:
push root node on stack
while (stack is not empty) {
pop node, print node
push node->right, push node->left
}
As stated before, recursion is never the only solution. You can always simulate the effects of the call stack using your own variables.
The other thing you have to watch for that can throw off timing is while loops. They will happily run forever, not allowing anything else to happen while doing so.
I so badly want AMX to give us an idle() function ...
How would that work if you didn't know the depth of the tree in advance?
Paul
Use a dynamic stack in languages that support it, or make it big enough to accomodate the largest possible tree. If you're talking about NetLinx, it sounds like a depth of 15 would be more than the call stack can handle anyway.
Make it big enough to accomodate the largest possible tree.
How big is the largest possible tree if you were to iteratively print file names starting at a root directory? I have to do this for a project but can't think of a way to figure that out at compile time in order to declare my variables.
Paul
How big is the largest possible tree if you were to iteratively print file names starting at a root directory? I have to do this for a project but can't think of a way to figure that out at compile time in order to declare my variables.
Paul
Use a dynamic stack, or figure out what your deepest possible tree is. Windows path names are limited to 260 characters, so 150 directories deep would be impossible.
Use a dynamic stack, or figure out what your deepest possible tree is. Windows path names are limited to 260 characters, so 150 directories deep would be impossible.
I don't have a dynamic stack unfortunately, and it has to be OS agnostic.
Paul
I don't have a dynamic stack unfortunately, and it has to be OS agnostic.
Paul
If you really can't come up with a reasonable upper bound for the depth, you could use parent pointers to go back up the tree instead. By keeping track of the previous node you looked at, you can tell whether you're coming or going:
node = root; prev = null;
while (node != null) {
if (prev == node->parent) { // came from parent, or starting from root (root->parent==null)
print node
if (node->left) next = node->left
else if (node->right) next = node->right
else next = node->parent
} else if (prev == node->left) { // came from left child, go right
if (node->right) next = node->right
else next = node->parent
} else if (prev == node->right) { // came from right child, go up
next = node->parent
}
prev = node; node = next
}
If you really can't come up with a reasonable upper bound for the depth, you could use parent pointers to go back up the tree instead. By keeping track of the previous node you looked at, you can tell whether you're coming or going:
node = root; prev = null;
while (node != null) {
if (prev == node->parent) { // came from parent, or starting from root (root->parent==null)
print node
if (node->left) next = node->left
else if (node->right) next = node->right
else next = node->parent
} else if (prev == node->left) { // came from left child, go right
if (node->right) next = node->right
else next = node->parent
} else if (prev == node->right) { // came from right child, go up
next = node->parent
}
prev = node; node = next
}
That's still reasonably elegant when dealing with a simple binary tree. But it gets very ugly quickly with more complex types of trees especially when adding/deleting nodes or rebalancing the tree.
Its trivial to replace the call stack with variables as you have shown. But there are still times when an iterative method is so complicated and ugly that recursion ends up being the only way. That was my whole point. I wasn't trying to say its always the preferred way, in fact I said I avoid it like the plague except when there is no other (reasonable) way. I would likely never use recursion in an embedded system unless it was dead simple like when using small, balanced binary trees of known maximum size and even then, the compiler would likely convert it to iterative code anyway.
Paul
But there are still times when an iterative method is so complicated and ugly that recursion ends up being the only way.
This is the only part I disagree with you about... recursion is never the only way. The most elegant way? Frequently. The fastest way? Sometimes. The only way? Never.
Comments
I've experimented with recursive functions in Netlinx and have had bad results. I don't think the subject of recursion is discussed in any of the AMX literature or training. I just assumed that it was not supported or "buggy" and moved on.
Actually, I think I remember what I was up to: somebody wanted to know how to calculate a nlog in Netlinx and in response I tried to write a recursive function to calculate the log based on a series expansion. The recursion kept blowing up so I just did it with a loop (as I recall). Looking at it again about a year ago, it seems that there was probably an easier way to do it, but then, something totally unimportant came up and I got distracted. Probably something like calculating the nlog of a negative number.
The non-recursive solution uses an explicit data structure (a stack) of nodes to traverse, rather than keeping that information on the call stack. In pseudo-code, for pre-order traversal:
push root node on stack while (stack is not empty) { pop node, print node push node->right, push node->left }As stated before, recursion is never the only solution. You can always simulate the effects of the call stack using your own variables.
I so badly want AMX to give us an idle() function ...
How would that work if you didn't know the depth of the tree in advance?
Paul
Use a dynamic stack in languages that support it, or make it big enough to accomodate the largest possible tree. If you're talking about NetLinx, it sounds like a depth of 15 would be more than the call stack can handle anyway.
How big is the largest possible tree if you were to iteratively print file names starting at a root directory? I have to do this for a project but can't think of a way to figure that out at compile time in order to declare my variables.
Paul
Use a dynamic stack, or figure out what your deepest possible tree is. Windows path names are limited to 260 characters, so 150 directories deep would be impossible.
I don't have a dynamic stack unfortunately, and it has to be OS agnostic.
Paul
If you really can't come up with a reasonable upper bound for the depth, you could use parent pointers to go back up the tree instead. By keeping track of the previous node you looked at, you can tell whether you're coming or going:
node = root; prev = null; while (node != null) { if (prev == node->parent) { // came from parent, or starting from root (root->parent==null) print node if (node->left) next = node->left else if (node->right) next = node->right else next = node->parent } else if (prev == node->left) { // came from left child, go right if (node->right) next = node->right else next = node->parent } else if (prev == node->right) { // came from right child, go up next = node->parent } prev = node; node = next }Adapted from: http://www.perlmonks.org/?node_id=600456 This is a pre-order traversal again, but can easily be adapted for different orders.That's still reasonably elegant when dealing with a simple binary tree. But it gets very ugly quickly with more complex types of trees especially when adding/deleting nodes or rebalancing the tree.
Its trivial to replace the call stack with variables as you have shown. But there are still times when an iterative method is so complicated and ugly that recursion ends up being the only way. That was my whole point. I wasn't trying to say its always the preferred way, in fact I said I avoid it like the plague except when there is no other (reasonable) way. I would likely never use recursion in an embedded system unless it was dead simple like when using small, balanced binary trees of known maximum size and even then, the compiler would likely convert it to iterative code anyway.
Paul
This is the only part I disagree with you about... recursion is never the only way. The most elegant way? Frequently. The fastest way? Sometimes. The only way? Never.