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