0

I've been working on this project, and I have this array set up that I populate with the following:

var myArray = {};
myArray[idNumber] = parentIdNumber;

Each member can only have one or no parent, denoted by 0. I have values up to 70 filled out.

I'm receiving a value input and need to check if every member of the array is in the 'family line' of input.

So I iterate through myArray and call isInFamilyLine(currentObject, 37), where currentObject is in the range 1-70:

function isInFamilyLine(idNumber, input) {
    if (idNumber== input) {
        isInLine =  true;
    } else {
        if (myArray[idNumber] == 0) {
            isInLine =   false;
        } else {
            isInLine = isInFamilyLine(myArray[idNumber], input);
        }
    }
    return isInLine;
}

I think the logic is right, but most examples I've seen of too much recursion involved a bug in the code.

What's also weird is that the too much recursion error is thrown on this line:

if (myArray[idNumber] == 0) {

Any ideas?

mechalynx
  • 1,306
  • 1
  • 9
  • 24
xHocquet
  • 362
  • 2
  • 11

2 Answers2

0

Given your code, what probably happens is, due to the bad input, nothing gets executed except your next call to isInFamilyLine which is also passed a bad parameter, giving rise to new calls to itself ad nauseum.

If myArray is an associative array, you need to make sure the values for the keys you're passing are of the proper type. You also need to check that whatever you're passing into the function turns out the way you want it and that you don't have any out-of-bounds issues with your array.

mechalynx
  • 1,306
  • 1
  • 9
  • 24
  • To complete the answer: `myArray[idNumber] == 0` resolves to `myArray[-69] == 0` which resolves to `undefined == 0` which is false, so the *else* branch is followed and keeps calling `isInFamilyLine` with exactly the same arguments. So any case where `myArray[idNumber] == 0` returns false will result in unlimited recursion. – RobG Jul 22 '14 at 03:31
  • @RobG But that's what I said :P – mechalynx Jul 22 '14 at 03:52
  • Sorry, don't know why I didn't clarify: As I'm looping through, the values 1 through 70 are being passed in (clarified in the post). – xHocquet Jul 22 '14 at 04:21
  • @user3707261 well even so, it seems like our interpretation would produce the exact result you get. Are you sure your input is indeed what you think it is? I noticed you mentioned that `myArray` is an associative array - are you perhaps passing strings instead of numbers for the indexes, or vice versa? What's the type of `CurrentObject`? – mechalynx Jul 22 '14 at 04:24
  • Care to explain the downvote? Is it because it answered the previous form of the question? Did you care to look at the comments before downvoting? – mechalynx Jul 22 '14 at 04:50
0

I see two possible problems:

Invalid input (thanks IvyLynx)

isInFamilyLine(x, "peanuts") leads to infinite recursion because x != "peanuts" for any sensible value of x and myArray["peanuts"] != 0 because undefined != 0. This leads to this line always being called:

isInLine = isInFamilyLine(myArray[idNumber], input);

So we have an infinite loop. Solution is to check if myArray[input] === undefined, then throwing an error and asking the user for a new value. This also ensure the input is within the expected range.

Note that because Javascript is weakly typed and you are using == instead of ===, "2" == 2, so receiving input numbers as string should not be the source of the problem.

Circular Structure

If myArray[x] == [x] for any x this code will also go into infinite recursion. You assume the values are acyclic but this may not be true. The same problem happen with cycles of any size, for example

myArray[1] = 2
myArray[2] = 3
myArray[3] = 1

If you only have 70 values a simple solution is to remember which members you have visited and to throw an error if you ever reach the same member twice. Or you could run a check before accepting any inputs, see How do I check if a directed graph is acyclic.

PS: I'm not sure but I think this algorithm is equivalent to verifying if every node in a tree is reachable or can reach a given input node. Modelling your data as an actual tree and using standard graph algorithms may help.

Community
  • 1
  • 1
BoppreH
  • 8,014
  • 4
  • 34
  • 71
  • I will double check when I get home to see if the first solution is my answer. Some clarifications: input is set as 37, there is no user input (yet). The graph is guaranteed in the direction because I have populated it myself with a list of members. A member's parent is only a number smaller than its ID or 0, no negatives. – xHocquet Jul 22 '14 at 14:05
  • Print the values to make sure. When we populate the values ourselves it's easy to fat finger a value. – BoppreH Jul 22 '14 at 16:44
  • Double checked values, got rid of some nulls with a check, and verified that all other values are good. I also added a check to make sure `myArray[input]` is not undefined, no dice. I left out a lot of code to simplify the question, but I might post the whole thing later if I can't figure it out, although this recursive function should be it... – xHocquet Jul 22 '14 at 18:08
  • When printing the values of `myArray[idNumber]` for the first line of `isInLine()`, I get a long repeated undefined. I added a check for `myArray[idNumber] === undefined` which returns `false`, what gives? – xHocquet Jul 22 '14 at 18:25
  • Try adding [`"use strict";`](http://stackoverflow.com/questions/1335851/what-does-use-strict-do-in-javascript-and-what-is-the-reasoning-behind-it?rq=1) to the top of your code. It might help catching the error. – BoppreH Jul 22 '14 at 18:35
  • How embarassing, the data got messed up and a bunch of ids were equal to their parent, so there was the problem. Wasn't able to see it because the tools I was using to see the data filtered stuff out uniquely... Answer goes to you for a bunch of error catching and bug fixes though, thanks! – xHocquet Jul 22 '14 at 19:40