On Sun, 5 Oct 2003 20:19:54 +0000 (UTC), "csx" <cs*@ms.com> wrote:
Ive got a problem with recursion in Javascript.
For this tree:
http://www.pcm.uklinux.net/structure.jpg
If you input node 3 (i.e. C) which is represented as 'values[2]' in the
array, it should return all the 'leaf' nodes. In this case 4!
Node 4 (i.e. D) is not included in the count.
In C, this function works perfectly:
int countLeafNodes(node& parentNode)
{
int sum = 0;
for (int j=0; j<nodes.size(); j++) {
if (parentNode.key == nodes[j].parent)
{
sum += countLeafNodes(nodes[j]);
}
}
return ((sum==0)?1:sum); // if node has no children sum is 0
}
The comment on the last line is wrong...
So are you a C programmer or did you find this example somewhere and
tried to translate it to this javascript:
function countLeafNodes(valuesCell)
{
var sum = 0;
temp = valuesCell.key;
This must be "var temp ...". var makes the variable a local variable
while not using var makes it global. You have to be especially aware
of the scope of your variables when you're dealing with recursion.
for (n=0; n < values.length; n++)
Must be "var n=0". See above.
{
if (temp == values[n].parent)
{
sum += countLeafNodes(n);
This is a problem I'll come back to shortly...
}
}
if (sum == 0) {
return 1; }
else {
return sum;
}
I would have left this written as
return ((sum==0)?1:sum);
or as
if (0 == sum)
sum = 1;
return sum;
for readability.
My guess is that you didn't write that C code, because if you had
you'd have been able to write the same thing in Javascript. You'll
have trouble writing a recursive function if you don't understand
what's going on. Try following your code and you'll find out pretty
quickly why you get a result of 1 instead of 4.
Code: var cols = countLeafNodes(values[2]);
Result: countLeafNodes gets the key property of values[2] which is 3
and then loops through the values array looking for items with a
parent property equal to 3. It finds the values[2] node, and calls
countLeafNodes(n).
<execution recurses into countLeafNodes>
Code: sum += countLeafNodes(n)
Result: countLeafNodes gets the key property of n which is undefined
because n is a number, not an object. (This is your main problem.)
Then it loops through the values array, looking for items with a key
property of undefined and obviously finds 0 nodes.
Code: if (sum == 0) return 1
Result: sum is 0, so returns 1
<execution leaves the recursive call to countLeafNodes, back to the
original countLeafNodes call>
The original countLeafNodes call is still in the loop. No more nodes
have a key value of 3 so no more calls to countLeafNodes are made and
at the end of the loop sum is still equal to 1.
I've changed it around a bit. But still no luck. I've been reading some
Javascript sites and I was wondering, do I need to use
arguments.callee
to get the recursion working? The examples are confusing. Some use it some
dont.
Recursion is primarily used for tree-like data structures. Your data
structure is flat (a simple array) though it logically describes a
tree which is not particularly an efficient way of doing things. That
said, this is the correct translation of the C code to work with your
flat data structure.
function countLeafNodes(valuesCell)
{
var sum = 0;
var temp = valuesCell.key;
for (var n=0; n < values.length; n++)
{
if (temp == values[n].parent)
{
sum += countLeafNodes(values[n]);
}
}
return (sum == 0 ? 1 : sum);
}
If you want to learn something, step through and figure out why you
need to use "var" with your temp and n variables, and why you have to
pass values[n] instead of n to countLeafNodes.
Now that the flat data structure is out of the way, here's the same
thing but with a tree structure.
<script language="javascript">
function information(key, desc)
{
this.key = key;
this.desc = desc;
this.parent = null;
this.row = 1;
this.subnodes = new Array();
this.addSubNode = function (node)
{
// Add the node to the subnodes array
this.subnodes.push(node);
// Set the node's parent and row
node.parent = this;
node.row = this.row + 1;
return node;
}
this.findNodeByKey = function (key)
{
var node = null;
if (this.key == key)
{
// This is the node we're looking for
node = this;
}
else
{
// Search each of the subnodes
for (var i=0; i<this.subnodes.length; i++)
{
// Another recursive function call...
node = this.subnodes[i].findNodeByKey(key);
// Stop looping when we've found the node
if (node)
break;
}
}
return node;
}
}
function countLeafNodes(node)
{
var sum = 0;
if (node.subnodes.length == 0)
{
// There are no subnodes so this is a leaf node
sum = 1;
}
else
{
// Recurse down through the subnodes
for (var i=0; i<node.subnodes.length; i++)
sum += countLeafNodes(node.subnodes[i]);
}
return sum;
}
// Build the tree structure.
// Notice that there is no parent or row information here.
// They are set correctly by addSubNode.
root = new information(1, 'A');
root.addSubNode(new information(2, 'B'));
C_node = root.addSubNode(new information(3, 'C'));
D_node = C_node.addSubNode(new information(4, 'D'));
C_node.addSubNode(new information(5, 'E'));
D_node.addSubNode(new information(6, 'F'));
D_node.addSubNode(new information(7, 'G'));
D_node.addSubNode(new information(8, 'H'));
// Count the leaf nodes under the C node
// Note: I could have used C_node instead of root.findNodeByKey(3)
// but that would have been no fun...
var cols = countLeafNodes(root.findNodeByKey(3));
document.write("The number of cols is: " + cols + "<br>");
</script>
Regards,
Steve
