Need to understand better this code

Question

I'm reading a JavaScript book, I'm new at this, so I got to the part of recursion and I get how recursion works but is not that part is hard to me is the math part.

This is the code:

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);

}

lets say I pass to the function 50 as a value right

isEven(50);

That give me true... how come 50 == 0 is true or 75 == 1 is false... I really don't get it.

The key is the very last line of the function. `50 == 0` is obviously *not* `true`, so when `n` is `50` it makes it all the way to that last line. — Pointy, Dec 22 '16 at 21:27
You obviously did not get the part about recursion. Go back to that part in the book. — PM 77-1, Dec 22 '16 at 21:27
using recursion to solve even no. problem doesn't seem to be a good choice. — Abhinav Galodha, Dec 22 '16 at 21:28
Try to find out how many times this function is being called... There lies the answer. — Mr. Hugo, Dec 22 '16 at 21:29
`isEven(50)` evaluates to `isEven(n - 2);` until it reaches `(n == 0`, returning `true`. because 50 is even, continually subtracting 2 will result in 0. 75 is odd, so that will eventually reach `n == 1`, resulting in `false` — Oliver, Dec 22 '16 at 21:30
Possible duplicate of [Understanding negative numbers in recursion](http://stackoverflow.com/questions/26473836/understanding-negative-numbers-in-recursion) — Prune, Dec 22 '16 at 21:31
@guest271314 Recursion isn't necessary to solve this problem. Like most examples in textbooks, it's just a toy problem. You also don't need to use recursion to calculate factorial, but it's a common example. — Barmar, Dec 22 '16 at 22:02
@Barmar Setting aside the definition of "recursion", as apparently the clear, unambiguous meaning of the term is not being inquired into at the present Question, nor addressed by any of the present Answers; the function at Question is not purely "recurive". If the function returns at either `if` or first `if..else` statement the function will not call itself again. — guest271314, Dec 22 '16 at 22:16
@guest271314 All recursive functions have a base case where they do something without recursing. Otherwise you'll never get a final result. — Barmar, Dec 22 '16 at 22:18
@Barmar Again, what is "recursion"? If we are to provide a definitive Answer, why should we not first define the terms used? What is the difference between "recursion", "repeated scheduling", "terminating procedure" and a "non-terminating procedure"? — guest271314, Dec 22 '16 at 22:21
@guest271314 https://en.wikipedia.org/wiki/Recursion#In_computer_science — Barmar, Dec 22 '16 at 22:22
@Barmar The Answer is to provide link to an editable wiki page? — guest271314, Dec 22 '16 at 22:23
@guest271314 I'm just trying to avoid having an extended discussion about the definition of "recursion", by referring you to a resource that shows a prototypical example of recursion. If you want to discuss the theory, write a question at cs.stackexchange.com. — Barmar, Dec 22 '16 at 22:50
@Barmar Is the Question not appropriate at stackoverflow? Where the term "recursion" is often used? Will write a Question here, for disambiguity. — guest271314, Dec 22 '16 at 22:51
@guest271314 Working programmers know what we mean by recursion, and the code in the question is a perfect example of it. We don't get bogged down in theoretical discussions, SO is for *practical* programming. — Barmar, Dec 22 '16 at 22:56
@Barmar Yes. Initially called the pattern at linked Question "recursion", here. Both answers stated it was not recursion. Not theory, but correct terminology for pattern used in practical usage setting. Is this not important? — guest271314, Dec 22 '16 at 22:58
@guest271314 The asychronous nature of promises doesn't really fit into the traditional definition of recursion. — Barmar, Dec 22 '16 at 23:04
@Barmar http://stackoverflow.com/questions/41292992/in-javascript-what-are-the-differences-between-recursion-a-non-terminating — guest271314, Dec 22 '16 at 23:13

score 2 · Answer 1 · answered Dec 22 '16 at 21:30

When you pass 50 to this function, it goes to the last block (else) and is executed recursively. When you write return isEven(n - 2);, you execute isEven(48), and then the next time isEven(46) and so on right upto the point where you reach isEven(0).

This calls the first if block and you get true as your output. The true is returned by isEven(0), followed by isEven(2) (becuase when you executed isEven(2) you ended up going to return isEven(0)) and this bubbles up the stack to finally return the output of isEven(50) as true.

score 2 · Answer 2 · answered Dec 22 '16 at 21:31

This code is kind of a long way of checking whether a number is even. It relies on the fact that if a number is even and you continually subtract 2 from it, you'll eventually reach 0. Otherwise, if your number is odd, subtracting 2 repeatedly will eventually reach 1.

So if the number you pass is greater than 0, it will send the next number (n - 2) back to the function again, until it either reaches 0 or 1. Then we stop.

If the number is negative, we just flip the sign and do the same process.

Will · Answer 3 · 2016-12-24T20:48:16.547

This is an interesting way of applying recursion to an issue that could be solved as simply as:

return n % 2 == 0

Basically, it works by having two base cases: n == 0 and n == 1. Both of these are "known", so they just return true or false. If the number is negative, do a recursive call with the sign reversed (isEven(-n)). Otherwise, you just subtract 2 (isEven(n - 2)). This works because any odd number minus 2 is still an odd number, and even number minus 2 is still even. So, you simply keep subtracting 2 from n until n fits one of the base cases (n == 0 or n == 1).

if (n == 0)          // base case
    return true;
else if (n == 1)     // base case
    return false;
else if (n < 0)      // reverse sign, call recursively 
    return isEven(-n);
else                 // default, subtracts 2, calls recursively 
    return isEven(n - 2);

score 0 · Answer 4 · answered Dec 22 '16 at 21:40

0

Use this tool to visualize your code and you'll see where you're getting hung up.

Click the Forward > button after the page loads to step through your code.

answered Dec 22 '16 at 21:40

gbeaven

1,522
2
20
40

score -1 · Answer 5 · answered Dec 22 '16 at 21:33

-1

You can simplify the function by using % operator

let isEven = n => !(n % 2);

answered Dec 22 '16 at 21:33

guest271314

1
15
104
177

3

How does this answer help him understand how recursion works? – Barmar Dec 22 '16 at 21:34
1

if he's having trouble understanding the original code, i'm not sure introducing clever one liners without explanation will help – Cruiser Dec 22 '16 at 21:34
1

He's not trying to tell if numbers are even, he's trying to learn about recursion. – Barmar Dec 22 '16 at 21:35
@Barmar Recursion is not necessary to return expected result for present Question. – guest271314 Dec 22 '16 at 21:35
4

You don't understand the question. He's not asking how to detect even numbers. He's reading the chapter of a textbook about recursion, and trying to understand the concept. It does him no good to just avoid the method entirely, then he'll still be ignorant of this important programming method. – Barmar Dec 22 '16 at 21:37
@Cruiser Good point. [Remainer (%)](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Arithmetic_Operators#Remainder_()) _"The remainder operator returns the remainder left over when one operand is divided by a second operand. It always takes the sign of the dividend, not the divisor."_ Here, we return `true` if `n % 2` is equal to `0`; we surround the expression with `!()` to return a `Boolean` opposition to `Boolean(0)`. – guest271314 Dec 22 '16 at 21:42

Need to understand better this code

5 Answers5