A JavaScript isEven() function, defined recursively

Question

Can someone please take a look at these recursive functions, offer some advice on the code, or just critique my attempt into thinking recursively?

Problem:

We’ve seen that % (the remainder operator) can be used to test whether a number is even or odd by using % 2 to see whether it’s divisible by two. Here’s another way to define whether a positive whole number is even or odd:

• Zero is even.
• One is odd.
• For any other number \$N\$, its evenness is the same as \$N - 2\$.

Define a recursive function isEven corresponding to this description. The function should accept a single parameter (a positive, whole number) and return a Boolean. - eloquentJavascript, chapter 3

My attempt:

function isEven(x) {
  if (x < 0 ) {
        return false
  }
   else if (x % 2 == 0) {
        return true
  } else {
        return isEven(x-2)
  }
}

Offical Solution:

function isEven(n) {
  if (n == 0)
    return true;
  else if (n == 1)
    return false;
  else if (n < 0)
    return isEven(-n);
  else
    return isEven(n - 2);
}

I know there are many ways to write the same piece of functionality but I want to know if the following code holds up to scrutiny. The official solution I checked my code against is obviously different but I'm getting the correct solutions.

console.log(isEven(50));
// → true
console.log(isEven(75));
// → false
console.log(isEven(-1));
// → false

What events does

else if (n < 0)
    return isEven(-n);

handle that,

 else
    return isEven(n - 2);

doesn't?

I started reading 'the little Schemer' on the advice of Douglas Crockford in an attempt to learn how to think recursively but the examples are in Scheme which just looks like ((( n ) * atom)) to me...so not very useful until I can read the syntax.

Answer 1

The solutions are nowhere near equivalent.

You're using the remainder operator %, when the whole point - I assume - is to not do that (for the purposes of the exercise - in any other case, definitely use %).

The official solution only knows how to answer true/false for the numbers 0 and 1. For any other input, it uses recursion to reduce the input all the way to either 0 or 1. It also flips negative numbers, in order to get those to 0 or 1*.

Your solution answers immediately for any positive, even number, without recursion. So you're sidestepping the whole exercise. And your code ends up making little sense, since, if you can answer true immediately, it follows that you can answer false immediately too. Those are the only possible return values, so if it's not true it logically must be false. Since you're not recursing for the first case, why would you bother to recurse for the second one?

In addition, your code treats all negative numbers as odd, unlike the official solution. And math in general.

To put all this another way: The official solution approaches the problem with this knowledge:

• 0 is even
• 1 is odd
• We don't know anything about the parity of other numbers
• But any number can be reduced to either 0 or 1 by repeatedly subtracting 2 and/or flipping the sign if the number's negative.

Hence the need to recurse for numbers that are not 0 or 1.

Your approach says:

• Numbers that can be cleanly divided by 2 are even (which is cheating)
• Negative numbers are odd (which is wrong)
• Any other number becomes negative if you keep subtracting 2

From the last point follows that any number that is not cleanly divisible by 2 is automatically an odd number. But you code doesn't make this leap, and instead uses (pointless) recursion.

Neither solution is by any means a good solution for determining the parity of a number(!), but the point (I assume, without knowing the context of the problem description) is to use recursion to drill down to something that can be answered categorically for specific numbers, i.e. 0 is even, 1 is odd. Your solution answers for sets of numbers, i.e positive even numbers and negative numbers.

_{*) For all of this we're assuming the input will always be a whole number, and not something else. Yes, you can do input validation, but that's beyond the scope of the exercise and this review}

Answer 2

Both of these seem horribly inefficient, but I guess that is what you get if you are forced to use recursion to solve this problem.

In either case you don't validate input. What if you don't get an integer value passed in the first place?

Your solution doesn't handle negative integers correctly - why would this always return false?

Your solution is really odd in that it unnecessarily uses recursion. If you are going to use modulus, you have no need to recurse at all. You know true or false directly after this operation and decrementing two from the number and recursing isn't going to change the outcome. It's just going to take more time until you finally get to value < 0.

I might have something more like the suggested solution, but with some input validation added:

function isEven(n) {
  // make sure we have a number
  if(isNAN(n)) {
    console.log('Non-integer passed to isEven()');
    return false;
  }
  // parse it as int to weed out floats
  if(n !== parseInt(n)) {
    console.log('Non-integer passed to isEven()');
    return false;
  }
  if (n === 0)
    return true;
  else if (n === 1)
    return false;
  else if (n < 0)
    return isEven(-n);
  else
    return isEven(n - 2);
}