Dave Thomas Dave Thomas - 5 months ago 11
Node.js Question

JavaScript recursion odd behaviour?

I'm having trouble understanding why a recursive function I wrote in JavaScript is having issues. When I feed it a large json file, it gets caught in an endless loop. I have a feeling it has something to do with how JavaScript closures work. Hopping some one smart can look at my code and explain what is going on.

I've ported the function line for line to PHP and it produces the output I expect.

JavaScript:

var jsonfile = process.argv[2];

json = require("./"+jsonfile);

path = "2";

buildPaths(json, path);

function buildPaths(json, path) {

if (json.Children == null || json.Children.length == 0) {

console.log(path + "/" + json.TypedItemId);

} else {

for (i = 0; i < json.Children.length; i++) {
buildPaths(json.Children[i], path + "/" + json.TypedItemId);
}
}

}


Ported to PHP:

<?php
$jsonfile = $argv[1];
$json = json_decode(file_get_contents($jsonfile));

$path = "2";

buildPaths($json, $path);

function buildPaths($json, $path) {


if ($json->Children == null || count($json->Children) == 0) {

echo $path . "/" . $json->TypedItemId . "\n";

} else {

for ($i = 0; $i < count($json->Children); $i++) {
buildPaths($json->Children[$i], $path . "/" . $json->TypedItemId);
}
}

}


Sample JSON file for testing with ( larger files cause even more weirdness ):

{
"TypedItemId": 4,
"Children": [
{
"TypedItemId": 67,
"Children": [
{
"TypedItemId": 90,
"Children": [
{
"TypedItemId": 90,
"Children": [
{
"TypedItemId": 67,
"Children": [
{
"TypedItemId": 90,
"Children": [
{
"TypedItemId": 90,
"Children": []
},
{
"TypedItemId": 908,
"Children": []
}
]
},
{
"TypedItemId": 908,
"Children": [
{
"TypedItemId": 90,
"Children": []
},
{
"TypedItemId": 908,
"Children": []
}
]
}
]
}
]
},
{
"TypedItemId": 908,
"Children": []
}
]
},
{
"TypedItemId": 908,
"Children": [
{
"TypedItemId": 90,
"Children": []
},
{
"TypedItemId": 908,
"Children": []
}
]
}
]
}
]
}


PHP Output ( correct ):

2/4/67/90/90/67/90/90
2/4/67/90/90/67/90/908
2/4/67/90/90/67/908/90
2/4/67/90/90/67/908/908
2/4/67/90/908
2/4/67/908/90
2/4/67/908/908


JavaScript Node output ( incorrect ) :

2/4/67/90/90/67/90/90
2/4/67/90/90/67/90/908

Answer

Nothing wrong with your JavaScript, except for the iterator you are using in your loop:

for (i = 0; i < json.Children.length; i++) {

Instead of declaring a local variable using var you are using a property i on the global object as an iterator, which is shared between all calls of buildPaths.

Use a local variable instead:

for (var i = 0; i < json.Children.length; i++) {

Try it yourself:

var json = {"TypedItemId":4,"Children":[{"TypedItemId":67,"Children":[{"TypedItemId":90,"Children":[{"TypedItemId":90,"Children":[{"TypedItemId":67,"Children":[{"TypedItemId":90,"Children":[{"TypedItemId":90,"Children":[]},{"TypedItemId":908,"Children":[]}]},{"TypedItemId":908,"Children":[{"TypedItemId":90,"Children":[]},{"TypedItemId":908,"Children":[]}]}]}]},{"TypedItemId":908,"Children":[]}]},{"TypedItemId":908,"Children":[{"TypedItemId":90,"Children":[]},{"TypedItemId":908,"Children":[]}]}]}]};

var path = "2";

buildPaths(json, path);

function buildPaths(json, path) {
    if (json.Children == null || json.Children.length == 0) {
        console.log(path + "/" + json.TypedItemId);
    } else {
        for (var i = 0; i < json.Children.length; i++) {
            buildPaths(json.Children[i], path + "/" + json.TypedItemId);
        }
    }
}