Compute if a natural number is even using single recursion.

Question

I know how to compute if a natural number is even by mutual recursion, logically:

EVEN_ZERO  -----------------
            (%even 0)  

            (%odd k)
EVEN_SUCC  -----------------
            (%even 1 + k)

            (%even k)
ODD_SUCC   -----------------
            (%odd 1 + k)

,which translates into the following functions:

(define is-even?
  (lambda (n)
    (if (= n 0)
        #t
        (is-odd? (- n 1)))))

(define is-odd?
  (lambda (n)
    (if (= n 0)
        #f
        (is-even? (- n 1)))))

However, I want to compute whether a natural number is odd using single recursion instead of mutual recursion. This should be possible, but I've trouble figuring out how to do it.

Could someone help me out?

Answer 1

Yes, subtract $2$ instead of $1$ until you either get $0$ (in which case the number is even) or you get $1$ (in which case the number is odd).

(define (parity n)
  (cond
    ((= n 0) 'even)
    ((= n 1) 'odd)
    (else (parity (- n 2)))))

The above code works correctly only for positive integers, but it is easy to modify it to work with all the integers by working with (abs n) instead of n.

Notice that the code is tail-recursive, so it runs in constant space.