This is my current function - I understand the premise of using recursion however can't seem to get the below function to return the index of the element - currently returning undefined.

My aim was to create a recursive version of this function (using a for loop:

// function searchIndex(arr, target) {
//     for(let i = 0; i < arr.length; i  ) {
//         if(arr[i] == target) {
//             return arr.indexOf(target);
//         }
//     }
//     return -1;
// }

my current code is as follows:

function searchRecursive(arr, target) {
    // base case
    if (arr[0] === target) {
        return 0;
    }
    else {
        searchRecursive(arr.slice(1), target)
    }
}

CodePudding user response：

Your current code has two main issues. The first is that your only return in your base case, which means the value that your recusive calls evaluate to are never returned in your else:

searchRecursive called with ([1, 2, 3], 3)
  searchRecursive called with ([2, 3], 3)
    searchRecursive called with ([3], 3)
      Base case reached, returning 0
    going back up to recursive call, nothing is returned, so function exits with `undefined`

Adding a return in your else won't simply fix the issue, because now you're only ever returning 0. You can however add 1 each time you recurse to indicate that you're now searching an additional index in the array. In addition, you also need to account for the case where you're unable to find your value to avoid recursing infinitely and accidentally exceeding the maximum call stack limit. To do that, you can add a check for when the array length is 0 and return -1 if you haven't found the item you're looking for yet:

function searchRecursive(arr, target) {
  if(arr.length === 0)
    return -1;
    
  if (arr[0] === target)
      return 0;

  const res = searchRecursive(arr.slice(1), target);
  return res === -1 ? res : 1   res;
}

console.log(searchRecursive([1, 2, 3, 4, 5], 3)); // 2

Alternatively, you can use tail recursion by adding an additional argument to keep track of the index you're currently looking at instead of slicing. This allows you to avoid creating new arrays for each recursive call, and is optimised for engines that are tail-call optimised (which is only Safari/WebKit as far as I'm aware):

function searchRecursive(arr, target, idx = 0) {
  if(idx === arr.length)
    return -1;
    
  if (arr[idx] === target)
    return idx;

  return searchRecursive(arr, target, idx   1);
}

console.log(searchRecursive([1, 2, 3, 4, 5], 3)); // 2

CodePudding user response：

here you have the same function in a recursive way:

function searchIndex(arr, target) {
  if (arr.length === 0) {
    return -1;
  }
  if (arr[0] === target) {
    return 0;
  }
  const index = searchIndex(arr.slice(1), target);
  if (index === -1) {
    return -1;
  }
  return index   1;
}

CodePudding user response：

You're pretty much there, you'd just need to return out the recursive call while also adding 1 to it:

function searchRecursive(arr, target) {
    if (arr[0] === target) {
        return 0;
    } else {
        return searchRecursive(arr.slice(1), target)   1;
    }
}

console.log(searchRecursive([1, 2, 3, 4, 5, 6], 3)); // -> 2

But, this approach is not very memory efficient. Each time your function is called, a copy of the array is made (excluding the first element), because .slice() always returns a brand new array. This copying is not necessary at all for your use-case.

Considering the general approach of a traditional for-loop, you can keep track of your place in the array using an "iterator" instead.

// Accept two parameters. The "index" parameter will only be used
// by the function when it calls itself.
function findIndex(arr, target, index = 0) {
    // If we've reached the end of the array and no element was
    // found, or if the array has no length to begin with, simply
    // return out -1.
    if (index   1 >= arr.length || !arr.length) return -1;
    // If the element at the current target index is a match,
    // return the index.
    if (arr[index] === target) return index;
    // If the element wasn't found, we'll increase our "index"
    // iterator value and test that index.
    return findIndex(arr, target,   index);
}
console.log(findIndex([1, 2, 3, 4, 5, 6, 7], 1)); // -> 0
console.log(findIndex([1, 2, 3, 4, 5, 6, 7], 4)); // -> 3
console.log(findIndex([1, 2, 3, 4, 5, 6, 7], 9)); // -> -1
console.log(findIndex([1, 2, 3, 4, 5, 6, 7], 6)); // -> 5

I also added a check for if the original array's length is zero. If it is, then the function doesn't need to do any work and can just return out -1 immediately.