Return 来自递归 indexOf 的正确值

Question

我写了一个递归函数来模仿 JavaScript 中的 .indexOf。

单步执行调试器时，除数组中不存在 item 参数外，一切都按预期工作。当 arr.length === 0 时触发停止条件，但随后调用堆栈展开并且 return 是数组的总长度。

如果 item 不存在，它应该 return -1。

我是递归的新手，我认为我可能遗漏了一段逻辑。感谢任何帮助。

function search(arr, item) {
    if (arr[0] === item) {
        return 0;
    }

    if (arr.length === 0) {
        return -1;
    }

    let remainingArr = arr.slice(1);

    if (arr[0] !== item && arr.length !== 0) {
         return 1 + search(remainingArr, item);
    }
}

Answer 1

如果结果是整数（0或更多），递归调用只加1；如果结果是 -1，return 只是 -1:

function search(arr, item) {
    if (arr[0] === item) {
        return 0;
    }

    if (arr.length === 0) {
        return -1;
    }

    const result = search(arr.slice(1), item);
    return result === -1 ? -1 : result + 1;
}

function search(arr, item) {
    if (arr[0] === item) {
        return 0;
    }

    if (arr.length === 0) {
        return -1;
    }

    const result = search(arr.slice(1), item);
    return result === -1 ? -1 : result + 1;
}

console.log(
  search([1, 2, 3, 4], 3),
  search([1, 2, 3, 4], -333),
);

Answer 2

我会将计数传递给递归调用。

另外，你的免责条款应该放在第一位。在 JS 中没那么重要，但是当数组中没有任何内容时 arr[0] === item 是没有意义的。

function search(arr, item, count = 0) {
  if (arr.length === 0) {
    return -1;
  }
  
  if (arr[0] === item) {
    return count;
  }

  return search(arr.slice(1), item, count + 1);
}

console.log(
  search([1, 2, 3, 4], 3),
  search([1, 2, 3, 4], -333),
);

实际上，这种方法可以不用 .slice(1)，因为 count 可以作为索引。

function search(arr, item, count = 0) {
  if (arr.length === count) {
    return -1;
  }
  
  if (arr[count] === item) {
    return count;
  }

  return search(arr, item, count + 1);
}

console.log(
  search([1, 2, 3, 4], 3),
  search([1, 2, 3, 4], -333),
);

Answer 3

数学归纳法可以指导您的程序。编号的步骤对应于程序注释中编号的行 -

如果位置 pos 超出数组范围，a、return -1
（归纳）位置在边界内。如果 a[pos] 匹配查询，q、return pos
（归纳）位置在边界内并且a[pos]与查询不匹配。 return 递归结果。

注意步骤的顺序很重要。例如，我们不想在检查 pos 是否越界（第 1 步）之前尝试读取 a[pos]（第 2 步）！

const search = (a, q, pos = 0) =>
  pos >= a.length
    ? -1                // 1
: a[pos] === q
    ? pos               // 2
: search(a, q, pos + 1) // 3

console.log(search(["a", "b", "c", "d"], "c")) // 2
console.log(search(["a", "b", "c", "d"], "z")) // -1

如果需要，您可以将 search 设为 higher-order 函数 -

const search = (a, f, pos = 0) =>
  pos >= a.length
    ? -1
: Boolean(f(a[pos]))
    ? pos
: search(a, f, pos + 1)

console.log(search(["a", "b", "c", "d"], v => v === "c")) // 2
console.log(search(["a", "b", "c", "d"], v => v > "a"))   // 1
console.log(search(["a", "b", "c", "d"], v => v > "z"))   // -1

您是否注意到当我们仅使用 [=66= 调用 search 时，第三个参数 pos 被分配的 默认值 为 0 ]两个个参数？

search([ 4, 99, 5, 8, 1, 9, 5, 11 ], 5) // pos = 0
// => 2

从 pos=3 开始，找到 5 -

的第一个位置也许有用

search([ 4, 99, 5, 8, 1, 9, 5, 11 ], 5, 3) // third argument; pos = 3
// => 5

但您可能不希望函数中有第三个参数。在这个修改中， loop 与我们的第一个函数具有相同的逻辑。 search 是 loop -

的简单包装

function search(a, q)
{ function loop(pos)
  { return pos >= a.length
      ? -1
    : a[pos] === q
      ? pos
    : loop(pos + 1)
  }
  return loop(0)
}

console.log(search(["a", "b", "c", "d"], "c")) // 2
console.log(search(["a", "b", "c", "d"], "z")) // -1

通过此更改，search 仅响应两个参数 -

search([ 4, 99, 5, 8, 1, 9, 5, 11 ], 5, 3) // third argument ignored
// => 2

Return 来自递归 indexOf 的正确值

Return correct value from recursive indexOf

javascript

recursion

return

indexof