CODEWITHSUNDEEP
javascriptrecursion
Robbie Milejczak
Robbie Milejczak

Reputation: 5770

Recursion and returning values in javascript

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.

Upvotes: 1

Views: 3184

Answers (3)

Tr1gZer0
Tr1gZer0

Reputation: 1712

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);

Upvotes: 1

kamoroso94
kamoroso94

Reputation: 1735

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;
    }
};

Upvotes: 0

Mark
Mark

Reputation: 92440

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.

Upvotes: 3

Related Questions