0
\$\begingroup\$

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ try -2 input to both functions. And using % and recursion is against the spirit of the problem as recursion was to avoid the complex % operation. \$\endgroup\$
    – Caridorc
    Aug 30 '16 at 22:02
9
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ +1 for good elaboration on functional differences between algorithms. I don't know that we can assume that we always get a whole number as input though as the problem statement as noted says "The function should accept a number parameter" as opposed to more specific integer or whole number specification. \$\endgroup\$
    – Mike Brant
    Aug 30 '16 at 22:33
  • \$\begingroup\$ @MikeBrant True, but considering that the "official" solution will choke on any non-integer, I choose to treat that as the "spec" – albeit implicitly \$\endgroup\$
    – Flambino
    Aug 30 '16 at 22:42
  • 1
    \$\begingroup\$ Note: % is no longer Modulo operator. It is Remainder Operator \$\endgroup\$
    – Tushar
    Aug 31 '16 at 9:35
2
\$\begingroup\$

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);
}
\$\endgroup\$
2
  • \$\begingroup\$ It's not unnecessary when it's a requirement: "Define a recursive function". \$\endgroup\$ Aug 30 '16 at 22:14
  • \$\begingroup\$ @DavidHarkness I understand the problem statement, but I guess I agree with the comment above that this would be against the spirit of trying to address this as a recursive solution, since you are not using recursion to actually make the determination is to whether the value is even. You could just as easily return false rather than making the recursion call. My guess is that the problem was intended to make you think outside the box of how one might normally solve this problem. \$\endgroup\$
    – Mike Brant
    Aug 30 '16 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.