How to find elements in array JavaScript where array[i] = i?

Question

I need to find elements in an array of numbers where arr[i] === i, meaning the element must be equal to the array index.
They must be found with using recursion, not just by cycle.
I would be very thankful, if someone help, because I've spent many hours and can't do anything.
I've tried to use Binary Search but it doesn't work. In the end I've got only the empty array.

function fixedPointSearch(arr, low, high) {

  let middle = Math.floor((high - low) / 2);
  
  console.log(  low, high, middle )
  
  let arrRes = [];
  if (arr[middle] === middle)
    { arrRes.push(arr[middle]); }
  else if (arr[middle] > middle)
    { fixedPointSearch(arr, middle + 1, high); }
  else
    { fixedPointSearch(arr, low, middle - 1); }

  return arrRes;
}
const arr1 = [-10, -3, 2, 3, 6, 7, 8, 9, 10, 12, 16, 17];
console.log(fixedPointSearch(arr1, 0, arr1.length - 1));

Answer 1

To do this recursively, you presumably want to recurse on smaller and smaller arrays, but that means you need to also update the index you're checking on each call. One of the simplest ways to do this is just to include an index in the parameters to your function and increment it on each recursive call. This is one way to do so:

const fixedPointSearch = ([x, ...xs] = [], index = 0) =>
  x == undefined
    ? [] 
    : [... (x === index ? [x] : []), ... fixedPointSearch (xs, index + 1)]

console .log (
  fixedPointSearch([-10, -3, 2, 3, 6, 7, 8, 9, 10, 12, 16, 17])
)

It's debatable whether that version or the following one is easier to read, but they are doing essentially the same thing:

const fixedPointSearch = ([x, ...xs] = [], index = 0) =>
  x == undefined
    ? [] 
  : x === index
    ? [x, ... fixedPointSearch (xs, index + 1)]
  : // else 
    fixedPointSearch (xs, index + 1)

There is a potential problem, though. Running this over a large array, we could hit the recursion depth limit. If the function were tail-recursive, that problem would simply vanish when JS engines perform tail-call optimization. We don't know when that will be, of course, or even it it will actually ever happen, even though it's been specified for five years. But it sometimes makes sense to write to take advantage of it, on the hope that it will one day become a reality, especially since these will still work as well as the non-tail-call version.

So a tail-recursive version might look like this:

const fixedPointSearch = ([x, ...xs] = [], index = 0, res = []) =>
  x == undefined
    ? res
    : fixedPointSearch (xs, index + 1, x === index ? [...res, x] : res)

Answer 2

If you want to find all the elements you should start from the beginning of the array, not the middle and loop through all the indexes.

The idea is for the recursion is to define the end condition.

Then you check if arr[i] === i to update the results array.

Then you make the recursive call with the index incremented and with the updated results array.

function fixedPointSearch(arr, i, results) {
  // End condition of the recursion
  if (i === arr.length - 1 || arr.length === 0) {
    return results;
  }
  
  if (arr[i] === i) {
    results.push(i);
  }
  
  // Recursive call
  return fixedPointSearch(arr, i + 1, results);
}
const arr1 = [-10, -3, 2, 3, 6, 7, 8, 9, 10, 12, 16, 17];

console.log(fixedPointSearch(arr1, 0, []));
console.log(fixedPointSearch([], 0, []));
console.log(fixedPointSearch([9, 8, 7], 0, []));

Answer 3

For recursion, you'll need an end condition. Something like

const findElementValueIsPositionInarray = arr => {
  let results = [];
  const find = i => {
    if (arr.length) {             // as long as arr has values
       const value = arr.shift(); // get value
       results = i === value      // check it
        ? results.concat(value)
        : results;
       return find(i+1);          // redo with incremented value of i
    }
    return results;
  };  
  return find(0);
}
console.log(findElementValueIsPositionInarray([2,3,4,3,9,8]).join());
console.log(findElementValueIsPositionInarray([2,3,4,91,9,8]).join());
console.log(findElementValueIsPositionInarray([0,1,2,87,0,5]).join());

.as-console-wrapper { top: 0; max-height: 100% !important; }

Answer 4

You can solve this w/o additional temporary arrays and parameters, by simply shortening the array in each step:

const myArray = [0, 5, 2, 4, 7, 9, 6];

function fixedPointSearch(arrayToTest) {
  if (arrayToTest.length === 0) {
    return [];
  }

  const lastIndex = arrayToTest.length - 1;
  const lastItem = arrayToTest[lastIndex];
  const remainingItems = arrayToTest.slice(0, lastIndex);

  return lastItem === lastIndex
    ? [...fixedPointSearch(remainingItems), lastItem]
    : fixedPointSearch(remainingItems);
}

console.log(fixedPointSearch(myArray));

Answer 5

The idiomatic solution in JavaScript uses Array.prototype.filter -

const run = (a = []) =>
  a.filter((x, i) => x === i)

console.log(run([ 0, 1, 2, 3, 4, 5 ])) // [0,1,2,3,4,5]
console.log(run([ 3, 3, 3, 3, 3, 3 ])) // [3]
console.log(run([ 7, 1, 7, 3, 7, 5 ])) // [1,3,5]
console.log(run([ 9, 9, 9, 9, 9, 9 ])) // []

Above it should be clear that recursion isn't required for the job. But there's nothing stopping you from using it, if you wish -

const filter = (test = identity, a = [], i = 0) =>
{ /* base */
  if (i >= a.length)
    return []
  
  /* inductive: i is in bounds */
  if (test(a[i], i))
    return [ a[i], ...filter(test, a, i + 1) ]
  
  /* inductive: i is in bounds, a[i] does not pass test */
  else
    return filter(test, a, i + 1)
}

const run = (a = []) =>
  filter((x, i) => x === i, a)

console.log(run([ 0, 1, 2, 3, 4, 5 ])) // [0,1,2,3,4,5]
console.log(run([ 3, 3, 3, 3, 3, 3 ])) // [3]
console.log(run([ 7, 1, 7, 3, 7, 5 ])) // [1,3,5]
console.log(run([ 9, 9, 9, 9, 9, 9 ])) // []

Answer 6

I don't know why you want it through recursion:- But anyway following should help you:-

let ans = [];

function find(arr,index,ans)
{
  if(index==arr.length-1)
    {
      if(arr[index]==index){
        ans.push(arr[index])
    }
    return;
}
  if(arr[index]==index){
      ans.push(arr[index])
}
  find(arr,index+1,ans);
}
const arr1 = [-10, -3, 2, 3, 6, 7, 8, 9, 10, 12, 16, 17];
find(arr1,0,ans);
console.log(ans);