javascript 如何编写一个递归函数来搜索数组以查找目标元素的索引(JS)

k0pti3hp  于 2023-01-07  发布在  Java
关注(0)|答案(3)|浏览(130)

这是我当前的函数-我理解使用递归的前提,但是似乎不能让下面的函数返回元素的索引-当前返回undefined。
我的目标是创建这个函数的递归版本(使用for循环:

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

我目前的代码如下:

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

yc0p9oo01#

当前的代码有两个主要问题,第一个问题是在基本情况下只使用return,这意味着递归调用的值不会在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 the recursive call, nothing is returned, so function exits with `undefined`

else中添加一个return并不能简单地解决这个问题,因为现在你只返回0,但是你可以在每次递归时添加1,以表明你正在数组中搜索一个额外的索引。
第二个问题是你还需要考虑到你找不到你的target值的情况,以避免无限递归和意外地超过调用栈的最大限制,为此,你可以添加一个检查,当数组长度是0时,如果你还没有找到你要找的项,就返回-1

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

或者,您可以使用tail recursion,通过添加一个额外的参数来跟踪您当前正在查看的索引,而不是切片。这允许您避免为每个递归调用创建新数组,并针对尾部调用优化的引擎和转发器进行了优化(据我所知,这只是Safari/WebKit)如果你担心性能,那么就用迭代方法来代替:

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
yquaqz18

yquaqz182#

这里你有一个递归的相同函数

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

oyt4ldly3#

现在你已经差不多做到了,你只需要返回递归调用,同时给它加1:

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

但是,这种方法不是很节省内存。每次调用函数时,都会复制一个数组(不包括第一个元素),因为.slice()总是返回一个全新的数组。这种复制对于您的用例来说是完全没有必要的。
考虑到传统for循环的一般方法,您可以使用“迭代器”来跟踪您在数组中的位置。

// 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

我还添加了一个检查,检查原始数组的长度是否为零,如果为零,则函数不需要做任何工作,可以立即返回-1

相关问题