Clojure Koans recursive is-even?

Question

I'm working through Clojure Koans and I'm up to the recursion koans.

I don't understand how to solve is-even? using recursion. The exercise partially defines this function as:

(defn is-even? [n]
    (if (= n 0)
        true
        (__ (is-even? (dec n)))))

If I don't want to use recursion then I would define it as (defn is-even? [n] (= (mod n 2) 0)) but that goes against the point of the exercise.

Answer 1

Like amalloy said, fill the blanks with "not". But provided you assume the argument can only be 0 or positive, you don't need another base case: dec makes sure you always end up at 0, and odd numbers return false like this:

(is-even? 0) ==> base case (= 0 0) ==> true.
(is-even? 1) ==> (not (is-even? (dec 1))
             ==> (not (is-even? 0))
             ==> (not true)
             ==> false
(is-even? 2) ==> (not (is-even? 1))
             ==> (not false)
             ==> true

etcetera.

Answer 2

A number n is even if either:

1. n is 0
2. n-1 is NOT even

So really, not should be enough to fill in that blank. Eventually you wind up with N nots around (= 0 0), and most of them cancel out.