I'm currently learning as much as I can about recursion but I'm really stuck on how to use it to check whether all the number elements in an array are even numbers. With ES6, I can use "every" to achieve the desire outcome as follow:

const isEven = (arr) => arr.every((item) => item % 2 === 0);
console.log(isEven([2,4,6,8])); // true
console.log(isEven([2,4,6,9])); // false

The following is my attempt as recursion:

const isEven = (arr) => (arr.length === 0) ? true : isEven(arr.slice(1)) % 2 === 0;
console.log(isEven([2,4,6,8])); // true
console.log(isEven([2,4,6,9])); // true

As you can see, the result is incorrect for the 2nd example and I have a feeling that I'm not on the right path either. Can someone kindly show me what I'm doing wrong?

CodePudding user response：

The problem with your implementation is that isEven returns a boolean but you try to use the result as if it is a number. So, it turns out that the return result is solely based on the number of elements, as each time it gets flipped:

console.log("true % 2 === 0 :", true % 2 === 0);
console.log("false % 2 === 0:", false % 2 === 0);

const isEven = (arr) => (arr.length === 0) ? true : isEven(arr.slice(1)) % 2 === 0;
console.log(isEven([]));     // true
console.log(isEven([1]));    // false
console.log(isEven([1, 1])); // true

If we write out your function fully instead as a single conditional operator, we can see what is happening better by adding some logging:

const isEven = (arr) => {
  if (arr.length === 0) {
    console.log("base case - finish recursion. result: true");
    return true;
  }
  const recursionValue = isEven(arr.slice(1));
  const result = recursionValue % 2 === 0;
  console.log(`After recursion: 
  recursionValue: ${recursionValue} 
  result        : ${result}`);
  return result;
}

console.log(isEven([2,4,6,9])); // true

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

Or to illustrate this differently, this is how the recursion will be resolved:

isEven([2,4,6,9])
| --> | isEven([4,6,9]) % 2 === 0
|     | --> | isEven([6,9]) % 2 === 0
|     |     | --> | isEven([9]) % 2 === 0
|     |     |     | --> isEven([]) % 2 === 0
|     |     |     |   | --> arr.length === 0 --> true
|     |     |     |   | true % 2 === 0 --> false
|     |     |     | false % 2 === 0  --> true
|     |     | true % 2 === 0 --> false
|     | false % 2 === 0 --> true
| true

To achieve what you want, you need to be checking the first element each time, not the result of isEven.

• If the array is empty, then the whole array must have been even. This is the base case. The recursion ends and the result is true
• If the first element is odd, then not all of the array is even. This is a terminal condition. End the recursion and return false - that means that the base case will not be reached.
• If there are items in the array and the first item is even, just recurse by using the rest of the array checking the above two conditions each time.

This ensures that you either get true if the second condition is never reached, or false if it ever is.

const isEven = (arr) => {
  if (arr.length === 0) // empty - base case
    return true;
  if (arr[0] % 2 === 1) // odd - stop and return false
    return false;
    
  return isEven(arr.slice(1)); // recursion
}

console.log(isEven([2,4,6,8])); // true
console.log(isEven([2,4,6,9])); // false

CodePudding user response：

The problem is in the isEven(arr.slice(1)) % 2 === 0 part. The isEven function is supposed to return a boolean, for which it doesn't make sense to to take the modulo.

Instead, you can do something like this:

isEven = arr => arr.length === 0 ? true : arr[0] % 2 === 0 && isEven(arr.slice(1));

CodePudding user response：

The premise should be:

The array is even if the first element is even and the rest of the array (which is also an array) is also even

So basically:

const isEven = (arr) => (arr.length === 0) ? true : arr[0] % 2 === 0 && isEven(arr.slice(1));

Which can be rewritten a little bit with destructuring to exemplify it better.

const isEven = ([first, ...rest]) =>
    (first % 2 === 0) &&
    (rest.length ? isEven(rest) : true);