1

I've recently been practicing writing recursive functions in JavaScript, and I've been running into a problem consistently when it comes to return values, which is that they ALWAYS seem to be undefined when returned from inside a conditional block.

Here is an example on jsFiddle

https://jsfiddle.net/g0dm68nm/

This is a simple binary sort implemented recursively. At this block of code

if (array[guess] === targetValue){
    console.log("equal");
    return(guess);
}

I see in my console "equal", which would never happen unless

    A) The variable guess is defined
    B) The item located at the index of that array equals the target search value

So I know that guess is absolutely defined or else my function would never evaluate the console.log statement, but the value returned is always undefined.

What am I missing? What is it that I am not understanding about recursion? This is the third function in the last 2 weeks I've written that behaves in the same way and I can't find any sort of answer anywhere online.

Improve this question
1
  • For this operation you don't need to use slice. Please see my answer below. Commented Jul 31, 2017 at 18:05

3 Answers 3

Reset to default
3

You need to return the call to the recursive function otherwise the values don't get passed on. For example:

// Added: return doSearch(array, targetValue);

let doSearch = function(array, targetValue) {
    let min = 0;
    let max = array.length - 1;
    let guess = Math.floor((max + min) / 2);

    if (array[guess] === targetValue) {
        console.log("equal");
        return guess;
    } else if (array[guess] > targetValue) {
        array = array.slice(0, guess);
        return doSearch(array, targetValue);
    } else if (array[guess] < targetValue) {
        array = array.slice(guess + 1);
        return doSearch(array, targetValue);
    } else {
        return "not in the list";
    }
};

Also, I suspect you want to return return array[guess] in the final return, which should give the number. By the time you've split the array on each recursion, the value of guess will be less than meaningful.

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

1 Comment

I remember trying to do this and get an error that my function wasn't defined, but I just tried it and it work perfectly so I must have made a typo. Thank you so much!
1

You need to use return. And probably change your code to keep track of min and max if you want the original index:

let doSearch = function(array, minI, maxI, targetValue) {
    let guess = Math.floor((maxI + minI)/2);
    if(array[guess] === targetValue) {
      console.log("equal");
      return guess;
    } else if (minI === maxI) {
      console.log("Not in list")
      return
    } else if (array[guess] > targetValue) {
      return doSearch(array, minI, guess, targetValue);
    } else if (array[guess] < targetValue) {
      return doSearch(array, guess+1, maxI, targetValue);
    }
};

let primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
        41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];

let result = doSearch(primes, 0, primes.length-1, 71);
Improve this answer

8 Comments

I agree that using slice is pretty bad, so I commend you for removing those calls. I just think the code would look nicer with a simpler function signature like before. Maybe use a nested function for the actual search implementation and have the outer function act as a wrapper that calls it with the initial arguments?
Totally agree with this!
@kamoroso94 I was using slice because the massive function calls and all the variable assignments looked ridiculous. It's a lot more concise and attractive with slice in place. I like your compromise though, I will give that a try!
You could move min and max to the end of the signature and set them to the default values if nothing is passes. (i.e. minI = typeof min === 'undefined' ? 0 : min maxI = typeof max === 'undefined' ? primes.length-1 : max ) Then you could call the function with just the array and guess.
@Mark_M Is there a reason you're using a ternary operator for the default parameters instead of just the default value?
|
0

You're missing a couple return statements. When you do a recursive call that gives you a value back, you need to do something with that value; in this case, return it. That is why you were getting undefined. The code was doing exactly what you asked, finding the item, but never passing it back up the call stack.

Edit: Secondly, (I missed this), since you are slicing up the array, the index of the solution in the sliced array isn't necessarily the same as that in the source array, so you should adjust for that when it gets shifted.

Edit 2: I would suggest using a common sentinel value like -1 rather than the string you're using when the value is not in the array.

let doSearch = function(array, targetValue) {
    let min = 0;
    let max = array.length - 1;
    let guess = Math.floor((max + min)/2);

    if(array[guess] === targetValue) {
      console.log("equal");
      return guess;
    } else if (array[guess] > targetValue) {
      array = array.slice(0, guess);
      return doSearch(array, targetValue);
    } else if (array[guess] < targetValue){
      array = array.slice(guess + 1);
      return doSearch(array, targetValue) + guess + 1;
    } else {
      return -1;
    }
};
Improve this answer

1 Comment

I would not use slice at all. Please see my answer.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.