Return correct value from recursive indexOf

Question

I've written a recursive function to mimic .indexOf in JavaScript.

When stepping through the debugger, everything works as expected except when the item argument is not present in the array. The stop condition is triggered when arr.length === 0 but then the callstack unwinds and returns the total length of the array.

If the item isn't present, it should return -1.

I'm new to recursion and think that I might be missing a piece of logic. Any help is appreciated.

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

Mathematical induction can guide your program. Numbered steps correspond to the numbered lines in the program comments -

1. if position, pos, is out of bounds of the array, a, return -1
2. (inductive) the position is in bounds. if a[pos] matches the query, q, return pos
3. (inductive) the position is in bounds and a[pos] does not match the query. return the recursive result.

NB the order of steps is important. For example, we don't want to attempt to read a[pos] (step 2) before we check if pos is out of bounds (step 1)!

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

You can make search a higher-order function, if you wanted -

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

---

Did you notice how the third parameter, pos, gets assigned a default value of 0 when we call search with only two arguments?

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

And maybe it's useful to say, starting at pos=3, find the first position of 5 -

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

But maybe you don't want that third parameter in the function. In this modification, loop has the same logic as our first function. search is a simple wrapper around 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

With this change, search only responds to two arguments -

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