Recursive function logic works but in one case the returned value is wrong?!

Recursive function logic works but in one case the returned value is wrong?!
0
#1

Please help me I’ve spent two hours unsuccessfully debugging this one case.

I used a recursive function to do this problem. It makes sense to do it this way as you can scale it. A for loop would go through the array one by one. My recursive function splits the array in two, puts the number in between, checks if it fits, if it’s to big cuts the second half in half and sticks it between those and repeats and if it’s too small cuts the first half in half… So less work than a for loop. And my code logically works!

But this ONE PARTICULAR CASE when the number has to fit at the end of the array, like a .push() method. Why doesn’t it work? Let’s go through it step by step.

  1. 15 can’t fit between 2 and 5 so put it between 5 and 10.
  2. 15 can’t fit between 5 and 10 so put it after 10.
  3. The index now turns this statement falsey: currentIndex > 0 && currentIndex < sortedArr.length
  4. The function should then skip the if statement and return currentIndex, or what the index would be after 10, or 3. The index is three. YET IT RETURNS 2 HOW CAN THIS BE?
function getIndexToIns(arr, num) {
  // Find my place in this sorted array.
  var sortedArr = arr.sort(function(a,b){
    return a-b;
  });
  
  function recursive(currentIndex){
        
    if(currentIndex > 0 && currentIndex < sortedArr.length){
      if(num > sortedArr[currentIndex-1] && num <= sortedArr[currentIndex]){
        return currentIndex;
      } else if (num <= sortedArr[currentIndex-1]){
        currentIndex = Math.floor(currentIndex/2);
        recursive(currentIndex);
      } else {
        currentIndex = Math.round(currentIndex + currentIndex/2);
        recursive(currentIndex);
      }
    } 
    return currentIndex;
  }
  
  return recursive(Math.floor(sortedArr.length/2));
}

getIndexToIns([2, 5, 10], 15);

Google Chrome Version 65.0.3325.181 (Official Build) (64-bit)

Your Browser User Agent is: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_13_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/65.0.3325.181 Safari/537.36.

Link to the challenge:

#2

I like the way you thought here

I’m not sure if you knew, but you’ve essentially reinvented a form of “binary search” in a recursive way. This is great, a much better way to search through a sorted list, though the non-recursive ways may perform better.

The problem is that you’re not returning when you ought to be. Try adding console.log("returning currentIndex: " + currentIndex); before your final return currentIndex. You should see a problem!

What you should actually be doing is, every time you call recursive, it should be via a return recursive(currentIndex); - the return is very important, otherwise it’s pointless to do so and will give the incorrect value.

#3

George thank you so much. But I’m sitting here going what the…?

Yes, the problem is visible with the console.log statements printing out currentIndex fifteen times (when it should only do it once!). Prepending the two calls to the function with the return keywords did solve the problem. I can’t wrap my head around what seems to have been solved here. If you don’t mind pasting my code to here (without the added two returns) you will see that the recursive function returns 3, then 2. I’m guessing that it may have something to do with the previous call to the same function, when the value was 2. I don’t know. I do want to learn how to return the 3 and stop any other returns from happening, to stop all the function calls that led to that 3… If you understand what I mean. I’m new to this but it does look very cool.

#4

With recursion we have a base case where we return a value, and the rest of the time we return the function with a modified parameter.

With your previous code, you were calling the function again but doing nothing with the result (including not returning!), and the function was falling through and getting to the final return instead.

It’s hard for me to phrase this well, but let’s look at a mega basic example you’ve no doubt seen before:

function factorial(n) {
    if (n === 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

When we use return we’re saying "the value of factorial(5)is 5 * factorial(4)", because that’s what the function returns.

Does that help in any way? It’s really hard for me to describe this better

#5

Thank you. Your answer helps but I’m going to have to study this. I thought that I only return when I have the final value, hence I only had it for when the num was in the right index or if it was 0 or sortedArr.length because it was less/greater than all the other values in the array. I didn’t think of returning every case when the recursive function had to be called, but I can follow the logic. Instead of calling it inside it returns, the value to the statement that called it, in this case the return statement at the end of the getIndexToIns() function. This way the recursive function calls itself over and over outside of its body (technically) in the getIndexToIns() return until the desired index value is reached. It’s obvious I am a novice in recursion and I won’t grasp for a while, so I don’t want to waste any more of your time, but your answer helps!

#6

What gebulmer said is absolutely true: the recursive calls without returning don’t make sense. In this problem, you should be using the return value of your function in some way!

I think it would be helpful if you named the function something descriptive of what it is actually doing. That would make its logic a lot clearer when you read the code. “recursive” is descriptive of its structure, but doesn’t tell you what its intended to do. “findInsertPosition” reads a lot better. The call to the function should even make sense when reading the line of code making the recursive call.

for example:

return n*factorial(n-1)

is clear as day! whereas

return n*recursive(n-1)

isn’t

Finally, in this specific case, double check your logic!
Consider an array that is 32 elements long and we’re searching it with your function.

  1. The first call gets the argument 16, so it’s checking positions 15 and 16.
    Say it decides it goes before 15.
  2. The recursive call gets the argument 8 (Math.floor(16/2):
    It checks positions 7 and 8. Let’s say its bigger than sortedArr[8]
  3. The next recrusive call gets the argument 12 (Math.round(8+4))
    It checks positions 11 and 12. Let’s say its bigger than sortedArr[12]
  4. The next recursive call gets the argument 18 (Math.round(12+6))
    ** But at step 1 we decided it goes before 15! So it can’t be right.

Your function is not a proper binary search… try using two arguments to represent the boundaries of the sub-array. I think if you do that, the picture will become clearer: your function’s purpose is to determine if an element belongs in the first half of the array or the 2nd. If you determine the element belongs in the first half, you can use the same (RECURISIVE) logic to figure out which half of the half it belongs in…

function findInsertPostion(fromIndex, toIndex) {...