Recursion troubles with "return undefined" (JavaScript)

Question

I'm stuck with recursion. I've read a few similar questions, but it brought me no relief. My function works well inside, but it returns "undefined" at the end.

I have a binary tree. Now I'm trying to make a function, which can get me an answer: if any nodes on this level have children.

class tree_node {
    constructor(n_array, parent) {
        this.n_array = n_array;
        this.has_children = false;
        this.children = [];
        if (parent != null) {
            this.parent = parent;
            this.level = this.parent.level + 1;
        }
        else {
            this.level = 0;
        }
        // run the tree
        this.child();
    }
    child() {
        if (this.n_array.length != 1) {
            this.has_children = true;
            let m = Math.floor(this.n_array.length / 2);
            let l = this.n_array.slice(0, m);
            let r = this.n_array.slice(m);
            const left = new tree_node(l, this);
            const right = new tree_node(r, this);
            this.children.push(left, right);
        }
        else return 0
    }

    get_if_node_has_children(node, level) {
        console.log(node.level, node.has_children)
        if (node.has_children && node.level < level) {
            console.log("in loop")
            node.children.forEach(element => {
                return element.get_if_node_has_children(element, level);
            });
        }
        else {
            console.log("first else")
            if (node.level == level && node.has_children) {
                console.log("node.level == level && node.has_children " + node.n_array)
                return true;
            }
            else {
                console.log("return false")
                return false;
            }
        }
    }
    show() {
        console.log(this.n_array + " | Level: " + this.level + ". " + this.branch + " Has children = " + this.has_children);
        if (this.has_children) {
            this.children.forEach(element => {
                return element.show();
            });
        }
        else {
            return 0;
        }
    }    
}

get_if_node_has_children(node, level) work inside, so to speak. I've expected the exact behaviour and log. Except on thing: function returns "undefined". But I have no idea where I missed the point.

let root = [];

class tree_node {
  constructor(n_array, parent) {
    this.n_array = n_array;
    this.has_children = false;
    this.children = [];
    // при создании экземпляра класса то parent == null
    if (parent != null) {
      this.parent = parent;
      this.level = this.parent.level + 1;
    } else {
      this.level = 0;
    }
    // run the tree
    this.child();
  }
  child() {
    if (this.n_array.length != 1) {
      this.has_children = true;
      let m = Math.floor(this.n_array.length / 2);
      let l = this.n_array.slice(0, m);
      let r = this.n_array.slice(m);
      const left = new tree_node(l, this);
      const right = new tree_node(r, this);
      this.children.push(left, right);
    } else return 0
  }

  get_if_node_has_children(node, level) {
    console.log(node.level, node.has_children)

    if (node.has_children && node.level < level) {
      console.log("in loop")
      node.children.forEach(element => {
        return element.get_if_node_has_children(element, level);
      });
    } else {
      console.log("first else")
      if (node.level == level && node.has_children) {
        console.log("node.level == level && node.has_children " + node.n_array)
        return true;
      } else {
        console.log("return false")
        return false;
      }
    }
  }

  show() {
    console.log(this.n_array + " | Level: " + this.level + ". " + "Has children = " + this.has_children);
    if (this.has_children) {
      this.children.forEach(element => {
        return element.show();
      });
    } else {
      return 0;
    }
  }
  // CLASS END ===========================
}

root = new tree_node([1, 3, 5, 7, 9, ])
console.log("=== root.show() ===")
root.show();
console.log("=== let a = root.get_if_node_has_children(root, 2) ===")
let a = root.get_if_node_has_children(root, 2)
console.log(" a is " + a)

return inside a forEach callback just returns from the callback, not the function the forEach is in. If you want to use return to exit the function, use for-of instead of forEach (it's less clunky anyway). — T.J. Crowder
– T.J. Crowder, Commented Jan 24, 2022 at 12:30
I've tried it before creating this question. It doesn't work either. With for-of the function stops after the first iteration. — Don Bobskiy
– Don Bobskiy, Commented Jan 24, 2022 at 12:38
That means you're returning unconditionally, without checking first if the value is waht you want. What is get_nodes_with_children supposed to do? It seems to return true or false, but the name suggests it should return a list or array of some kind. — T.J. Crowder
– T.J. Crowder, Commented Jan 24, 2022 at 12:40
Sorry, it was an old name from another attempt. Let say its name is get_if_node_has_children I can't see where I'm wrong in my logic... First I check - if the node has children and the level is higher. If so - I go into recursion. If the level is the one I want to check - then if it has children - I return true, otherwise - false. — Don Bobskiy
– Don Bobskiy, Commented Jan 24, 2022 at 12:47

T.J. Crowder · Accepted Answer · 2022-01-24 13:04:52Z

1

There are two problems:

return inside a callback (for instance, your forEach callback) just returns from the callback, not the function that called forEach. In general, in modern code, use for-of unless you need the index of the element.
You're not checking the result of the recursive call before returning it. But if the first child node you call it on returns false, you want to keep looking, rather than immediately returning false.

Fixing both:

get_if_node_has_children(node, level) {
    console.log(node.level, node.has_children)
    if (node.has_children && node.level < level) {
        console.log("in loop")
        for (const element of node.children) { // *** #1, using `for-of` instead of `forEach` so we can return below
            const hasChild = element.get_if_node_has_children(element, level);
            if (hasChild) {     // *** #2, only return here if you got `true`
                return true;    // *** 
            }                   // *** 
        }
        return false; // *** #2 part 2 -- didn't find it anywhere, return `false`
    } else {
        console.log("first else")
        if (node.level == level && node.has_children) {
            console.log("node.level == level && node.has_children " + node.n_array)
            return true;
        } else {
            console.log("return false")
            return false;
        }
    }
}

I'd reorganize that slightly though, which is easier if I remove some no-longer-needed logging:

get_if_node_has_children(node, level) {
    console.log(node.level, node.has_children)
    if (node.has_children) {
        if (node.level === level) {
            return true;
        }
        if (node.level < level) {
            for (const element of node.children) {
                if (element.get_if_node_has_children(element, level)) {
                    return true;
                }
            }
        }
    }
    return false;
}

edited Jan 24, 2022 at 13:04

answered Jan 24, 2022 at 12:53

T.J. Crowder

1.1m201 gold badges2k silver badges2k bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Don Bobskiy Over a year ago

Thanks a lot. I'll think about it deeper, I still can't get this recursion topic completely. But few questions. First - why const but not let. Second - is there any profit using const hasChild = element.get_if_node_has_children(element, level); but not strite away if (element.get_if_node_has_children(element, level))

T.J. Crowder Over a year ago

@DonBobskiy - Why not const? We never change the value of element. I habitually use const for any binding (loosely, "variable") that I don't intend to change the value of. But let is fine too. Re the second: Thanks for pointing that out, that was a holdover from an earlier version and I should have consolidated those. :-) I've fixed it.

Don Bobskiy Over a year ago

Thank you, now all sounds more clear. I understand now (and you've said it but I didn't get it first:) that my mistake was not checking node.has_children before using return...

Collectives™ on Stack Overflow

Recursion troubles with "return undefined" (JavaScript)

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related