Recursive even function issue with understanding (Javascript)

Question

The problem is very simple, I have a function from 'Javascript Allonge' book, and having a hard time in understanding it.

The function is called even, and it's as follows:

var even = function(num) {
    return (num === 0) || !(even(num -1));
}

it checks whether the number is even or not, but I do not understand how. It calls itself recursively, and technically, always reaches zero, no? How does that work?

Answer 1

This is based on an inductive definition of numbers being odd or even - a number, n is 'even' when the number before it, n - 1 is odd. This thinking naturally makes sense - 4 is even if 3 is odd.

And so the function even is defined as:

1. even(0) is true - because 0 is even

2. even(n) is the negation of even(n - 1)

Another way to think of it is imagine even(4) being called step by step. By hand, replace the even(4) with result of evaluation it with your function:

even(4)
= !(even(3))
= !(!even(2))
= !(!(!even(1))
= !(!(!(!even(0)))
= !(!(!(!true))
= true


// ...even(4) == true

Answer 2

Well, divide and conquer.

First of all you have two expressions to calculate. The first one is just stopping the recursion at the point when the number is 0, this is easy.

The second expression

!(even(num -1))

is a bit more complicated. It always starts with a call even(num -1) and then negates it.

For the first element !(even(num -1) === true), so now you see that for every second element starting from 1 (1, 3, 5 etc.) it will return false, for others the inverted value.