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)
        (is-odd? (- n 1)))))

(define is-odd?
  (lambda (n)
    (if (= n 0)
        (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?

  • $\begingroup$ I've answered your question but I believe that it was more appropriate for StackOverflow. $\endgroup$ – Alex M. Nov 5 '16 at 11:35

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)
    ((= 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.

  • $\begingroup$ Ahh, of course every (positive) integer can be represented as $2k + i$, where $k \ge 0$ and $i = 0 \text{ or } 1$. Thanks. $\endgroup$ – Shuzheng Nov 5 '16 at 11:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.