Recursion problems - how does it work?

C

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>
 
C

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>
 
S

Steve van Dongen

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
}
Click to expand...
Click to expand...

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;
Click to expand...
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++)
Click to expand...
Must be "var n=0". See above.
{
if (temp == values[n].parent)
{
sum += countLeafNodes(n);
Click to expand...
This is a problem I'll come back to shortly...
}
}

if (sum == 0) {
return 1; }
else {
return sum;
}
Click to expand...

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.
Click to expand...

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.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);
}

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

C program: memory leak/ segmentation fault/ memory limit exceeded 0
macro recursion 11
Dont work, it´s something whit the loops? 1
How can I calculate the last payment for Reprofiled Amount column with 2 decimal places to make the sum of all payments to be the same as RC amount? 2
Simple functions don't work :( 3
SENTINEL CONTROL LOOP WHEN DEALING WITH TWO ARRAYS 1
Difference between using "let" in a "for" loop 0
Trouble with prediction code, for the life of me I can't figure out why it isnt running properly. Help would be appreciated. 0

Members online

No members online now.
Total: 36 (members: 0, guests: 36)
Robots: 114

Forum statistics

Threads
473,772
Messages
2,569,593
Members
45,112
Latest member
VinayKumar Nevatia

Latest Threads

Top