Javascript recursion caused circular structure

Question

I have the following 2D array cells:

ID  Name    Parent
1   Bob     0
2   Alice   1
3   John    2
4   Jane    2
5   Jenny   3
6   Jonny   2

I want to convert it into nested JSON format, such that each object has the following attributes:

name
Array of children, which includes also objects with names and arrays of children. There are no circular nestings in the array; a child can't have any of its parents as children.

Here is the function I wrote:

function getChildren(node){
    console.log('Getting Children for' + node)
    children = []
    for(i = 0;i < cells.length; i++){
        if(cells[i][2] == node){
            cell = cells[i]
            child = {}
            child.name = cell[1]
            child.children = getChildren(cell[0])
            children.push(child)
        }
    }
    return children
}


text = "ID  Name    Parent\n1   Bob     0\n2   Alice   1\n3   John                  2\n4   Jane    2\n5   Jenny     3\n6   Jonny   2\n"

lines = text.split('\n')
cells = []
for(i = 0; i < lines.length; i++){
    cells[i] = lines[i].split(/\ +/)
}

Calling the function on node 6 getChildren(6), gives this output:

Getting Children for6
[]

Which is correct because node 6 has no children.

But calling the function on nodes with children, for example getChildren(3), gives:

Getting Children for3
Getting Children for5

Object
    children: Array[1]
        0: Object
            children: Array[1]
                0: Object
                    children: Array[1]
                    name: "Jenny"
                    length: 1
            name: "Jenny"
            length: 1
    name: "Jenny"

From the console output it seems like it calls the right functions, but why is the object for "jenny" infinitely nested under all children?

I want to end up with a JSON object that I could use JSON.stringify on. Calling the function on getChildren(3) gives the error

Uncaught TypeError: Converting circular structure to JSON.

I think this is because the object for Jenny is infinitely nested under each child.

Please show the actual Javascript data structure you start with and exactly what you want to end up with in legal Javascript data definition or string format. Showing a table doesn't tell us exactly how it is structured in code. We can guess, but then you're supposed to disclose enough that we don't have to guess. — jfriend00
It is there in the fiddle link, I start with a string that I parse into a table, I want to convert it into json at the end, each object has a name, and an array of children, which are also objects with names, and arrays of children — Mohab
Per the guidelines for this site, it should be pasted directly into your question, not only in the jsFiddle link. External links have a habit of getting changed or disappearing over time ruining the most important content of the question and thus rendering the question much less useful as a long term reference. Also, do you realize that JSON is a string format, not an object format. Is that really what you want? You should show the exact data definition you start with and the exact data definition you want to end with and then you'd need only a few words around that to be 100% clear. — jfriend00
the global variables probably aren't helping either, especially considering you're using a recursive function. — Kevin B
Ok I added the complete code, and the final output I want to end up with — Mohab

trincot trincot · Accepted Answer · 2016-10-20T22:04:03

You use global variables, and as a consequence, when you call your function recursively, variables like children and child can get new values. When you come back out of the recursive call, you do:

children.push(child)

.. but children will have taken another value than you expect, and so can child also have a different value, both from what they were in the recursive call (or from even deeper into the recursion).

For the same reason the recursive modification of i will lead to problems.

Use var to make your variables local to your function, and it will work:

function getChildren(node){
    console.log('Getting Children for' + node)
    var children = []
    for(var i = 0;i<cells.length; i++){
        if(cells[i][2] == node){
            var cell = cells[i]
            var child = {}
            child.name = cell[1]
            child.children = getChildren(cell[0])
            children.push(child)
        }}
    return children
}

function getChildren(node){
    var children = []
    for(var i = 0;i<cells.length; i++){
        if(cells[i][2] == node){
            var cell = cells[i]
            var child = {}
            child.name = cell[1]
            child.children = getChildren(cell[0])
            children.push(child)
        }}
    return children
}

var text = "ID  Name    Parent\n1   Bob     0\n2   Alice   1\n3   John                  2\n4   Jane    2\n5   Jenny     3\n6   Jonny   2\n"

var lines = text.split('\n')
var cells = []
for(var i = 0; i< lines.length; i++){
  cells[i] = lines[i].split(/\ +/)
}

console.log(JSON.stringify(getChildren(0), null, 2));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Javascript recursion caused circular structure

3 Answers