Why does this recursive javascript function return what it does?

Question

var fn = function even (n) {
  if (n === 0) {
     return true
  }
   else return !even(n - 1)
 }

 fn(5)//=> false

 fn(2)  //=> true

Why does this function work the way it does? When I step through it when the argument is 5 it seems to call itself until n is zero which would return true but it returns false.

It is because every recursive call reverse the value of the boolean, so if it is a multiple of 2 it will return true . Any other vase would be false — Matriac
– Matriac, Commented Mar 11, 2016 at 13:26
On each recursive call, the returned value is negated. Then !!!!!false is true. In short: The result is negated when ! is applied odd times — Tushar
– Tushar, Commented Mar 11, 2016 at 13:28
The same function can be rewritten using modulo operator as function isEven(num) { return num % 2 === 0; } — Tushar
– Tushar, Commented Mar 11, 2016 at 13:30
@Tushar, instead of the expensive modulo you can use bit-operations for this: var isEven = n=> (n&1)===0 or var isEven = n => !(n&1); but this is OT — Thomas
– Thomas, Commented Mar 11, 2016 at 13:39

Tushar · Accepted Answer · 2016-03-11 13:33:34Z

5

Every recursion step adds a negation to the previous result:

f(0) = true
f(1) = !f(0) = !true = false
f(2) = !f(1) = !!f(0) = !!true = !false = true

and so on, for f(5) you get

f(5)
    !f(4)
        !!f(3)
            !!!f(2)
                !!!!f(1)
                    !!!!!f(0)
                    !!!!(!true)
                !!!(!false)
            !!(!true)
        !(!false)
    !true
false

edited Mar 11, 2016 at 13:33

Tushar

87.4k21 gold badges164 silver badges182 bronze badges

answered Mar 11, 2016 at 13:25

Matteo Tassinari

18.6k8 gold badges65 silver badges85 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Adam1980 Over a year ago

I didn't realize that the ! would accumulate. Thanks for the great answer.

Walfrat · Accepted Answer · 2016-03-11 13:25:46Z

0

it's because of the !

When the function is 0 it return true.

When it's 1 it will return !even(0) -> false.

When it's 2 it will return !even(1) => !(!even(0)) => !(false)=> true.

Since boolean is either true of false, meaning two possible value and you switch them again and again it works.

answered Mar 11, 2016 at 13:25

Walfrat

5,3941 gold badge18 silver badges36 bronze badges

Collectives™ on Stack Overflow

Why does this recursive javascript function return what it does?

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related