# A Tale of Two Functions

When covering the matter of mutually-recursive functions the first Edition of Programming F# comes up with the following sample on page 55:

let rec isOdd n = (n = 1) || isEven (n - 1) and isEven n = (n = 0) || isOdd (n - 1)

Looks beautiful, but unfortunately does not work. The second Edition Programming F# 3.0 attempts fixing the problem with the following code on page 60:

let rec isOdd x = if x = 0 then false elif x = 1 then true else isEven(x - 1) and isEven x = if x = 0 then true elif x = 1 then false else isOdd(x - 1)

This snippet works correctly, but it got four times longer, than the original and apparently smells. May it be refactored towards DRY? Sure, for example:

let rec isOdd = function | 0 | 1 as n -> (n = 1) | n -> isEven (n - 1) and isEven n = isOdd (n - 1)

Good, but still 100% longer, than the original, so let’s keep trying:

let rec isOdd n = if n >= 2 then isEven (n - 1) else n = 1 and isEven n = if n >= 2 then isOdd (n - 1) else n = 0

Cool, this works correctly and is as succinct as the original. But wait a minute, boolean **if-then-else** expression can be rewritten to the equivalent expression using **&&** and **||** operators:

let rec isOdd n = n >= 2 && isEven (n - 1) || n = 1 and isEven n = n >= 2 && isOdd (n - 1) || n = 0

Almost perfect, but what if we out of curiosity try something like **isOdd 10000000**? Oh,no! Although equivalent to previous snippet, the latest one gets not tail-recursive and blows the stack.

OK, let’s convert it back to a tail-recursive equivalent:

let rec isOdd n = n = 1 || n >= 2 && isEven (n - 1) and isEven n = n = 0 || n >= 2 && isOdd (n - 1)

or even to just another tail-recursive equivalent:

let rec isOdd n = n < 2 && n = 1 || isEven (n - 1) and isEven n = n < 2 && n = 0 || isOdd (n - 1)

The latest snippet is almost similar to the original, but works perfectly.

The bottom line: often a boolean expression may perfectly substitute one built with **if-then-else**. But watch for subtleties, like inadvertently losing tail-recursiveness.

This blog was… how do I say it? Relevant!! Finally I have found something which

helped me. Appreciate it!

What is is not ok to just write:

let rec isOdd n = not (n = 0) && isEven (n – 1)

and isEven n = (n = 0) || isOdd (n – 1)

, assume we ignore negative numbers?

Phil, nothing is “wrong” with your snippet, it is algorithmically correct. Although seeing its correctness and the way it works is, in my opinion, harder, than for one based on logical OR only, as was the original intent of Chris Smith in the book.