recursive function that calls recursion inside for loop in javascript

Question

I have a class for a Street which is just a line with a beginning point and an end point, inside this same class I have a function called checkIntersections which :

checks if this Street intersects with a given Street and its children which are also of type Street.
returns true at the first found intersection
returns false or undefined if no recursive intersections were found

I decided to make checkIntersections a recursive function but I think I'm going about it wrong because nested intersections between streets are not being detected.

  checkIntersections(street){

if(intersects(this.beginning, this.end, street.beginning, street.end)){
  return true;
}
else{
  for(var i = 0 , count = street.children.length ; i < count ; i++){
    this.checkIntersections(street.children[i]);  
  }
}

}

Is there anything that I should be attentive to while making recursive calls inside a for loop in javascript ? The output of the function is always undefined.

I think all this.checkIntersections(street.children[i]) values must be evaluated and returned instead of returning the result of the first index. — Ramesh Reddy
– Ramesh Reddy, Commented Dec 31, 2021 at 11:15
I was under the impression that my code did what you just described. Would you give me a pointer as to what I've missed ? Thanks — Kaspie
– Kaspie, Commented Dec 31, 2021 at 11:22
when you use the return statement the rest of the iterations will not happen, so you have to return after lopping everything — Ramesh Reddy
– Ramesh Reddy, Commented Dec 31, 2021 at 11:24
if any of the children intersect, does that mean the parent street intersects? Or should all children intersect? — Ramesh Reddy
– Ramesh Reddy, Commented Dec 31, 2021 at 11:26
I've updated my question giving more details on this, the function should returns true at the first found intersection, and return false or undefined if no recursive intersections were found. Following your advice I've also updated the code to not use the return statement inside the for loop. But now all I get are undefined outputs — Kaspie
– Kaspie, Commented Dec 31, 2021 at 12:37

trincot · Accepted Answer · 2021-12-31 12:42:22Z

2

Your code is not using the value returned from the recursive call -- it just ignores it and just continues with the next recursive call. Instead it should detect a success from a recursive call and then exit immediately, returning that success to its own caller.

checkIntersections(street) {
    if (intersects(this.beginning, this.end, street.beginning, street.end)) {
        return true;
    } else {
        for (let child of street.children) { // Use modern for..of loop
            let success = this.checkIntersections(child);
            if (success) return true; // bubble up the happy result!
        }
    }
}

answered Dec 31, 2021 at 12:42

trincot

357k38 gold badges282 silver badges338 bronze badges

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

4 Comments

Kaspie Over a year ago

Thank you so much ! I think it makes sense now, I was expecting the 'return true' in my if statement to return true recursively, but I realize now that my function this.checkIntersections(child) returned 'true' and not 'return true' Thanks again for helping it works perfectly

Scott Sauyet Over a year ago

Wouldn't something like ... else {return street.children.some(child => this .checkIntersection (child))} (untested) be both simpler and more explicit?

trincot Over a year ago

@Scott, sure, but this answer focuses on the problem in the Asker's code, so I kept the explicit loop.

Scott Sauyet Over a year ago

Yes of course. I wasn't thinking straight.

Gabriele Petrioli · Accepted Answer · 2021-12-31 12:49:09Z

1

It should be something like

checkIntersections(street) {
  if (intersects(this.beginning, this.end, street.beginning, street.end)) {
    return true;
  } else if (street.children.length) {
    return street.children.some( checkIntersections );
  }
  return false;
}

you need to return the recursive call to checkIntersections
it would be better to use .some for the children as it will do a early exit
you need to provide a default return in case there are no children and the current intersection failed.

edited Dec 31, 2021 at 12:49

answered Dec 31, 2021 at 12:43

Gabriele Petrioli

197k35 gold badges275 silver badges331 bronze badges

Collectives™ on Stack Overflow

recursive function that calls recursion inside for loop in javascript

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related