By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,564 Members | 1,070 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,564 IT Pros & Developers. It's quick & easy.

Recursion problems - how does it work?

P: n/a
csx
Hi all,
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
}
I've tried to replicate this code in Javascript. But the recursion just
doesnt work. Has anyone got any suggestions? Any help would be much
appreciated.

Here's the JavaScript code at the moment.
<html>
<head>

<script language="javascript">
function values(key, row, desc, parent)
{
this.key = key;
this.row = row;
this.desc = desc;
this.parent = parent
}
</script>

<script language="javascript">
function countLeafNodes(valuesCell)
{
var sum = 0;
temp = valuesCell.key;

for (n=0; n < valuesCell.length; n++)
{
if (temp == valuesCell[n].parent)
{
sum += countLeafNodes(valuesCell[n]);
}
}

if (sum == 0) {
return 1; }
else {
return sum;
}

</head>
<body>
values = new Array();

values[0] = new information(1, 1,'A',0);
values[1] = new information(2, 2,'B',1);
values[2] = new information(3, 2,'C',1);
values[3] = new information(4, 3,'D',3);
values[4] = new information(5, 3,'E',3);
values[5] = new information(6, 4,'F',4);
values[6] = new information(7, 4,'G',4);
values[7] = new information(8, 4,'H',4);

var cols = countLeafNodes(values[2]);
document.write("The number of cols is: " + cols + "<br>");

</script>

</body>
</html>
Jul 20 '05 #1
Share this Question
Share on Google+
3 Replies


P: n/a
csx
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.

<html>
<head>
</head>
<body>

<script language="javascript">
function information(key, row, desc, parent)
{
this.key = key;
this.row = row;
this.desc = desc;
this.parent = parent
}

function countLeafNodes(valuesCell)
{
var sum = 0;
temp = valuesCell.key;

for (n=0; n < values.length; n++)
{
if (temp == values[n].parent)
{
sum += countLeafNodes(n);
}
}

if (sum == 0) {
return 1; }
else {
return sum;
}
}

values = new Array();
values[0] = new information(1, 1,'A',0);
values[1] = new information(2, 2,'B',1);
values[2] = new information(3, 2,'C',1);
values[3] = new information(4, 3,'D',3);
values[4] = new information(5, 3,'E',3);
values[5] = new information(6, 4,'F',4);
values[6] = new information(7, 4,'G',4);
values[7] = new information(8, 4,'H',4);

var cols = countLeafNodes(values[2]);
document.write("The number of cols is: " + cols + "<br>");

</script>
</body>
</html>
Jul 20 '05 #2

P: n/a
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
Jul 20 '05 #3

P: n/a
csx
Steve,
Thankyou so much for the time and effort in helping!

kind regards!
Jul 20 '05 #4

This discussion thread is closed

Replies have been disabled for this discussion.