These functions are based on the observation that the question "is 4 even?" is equivalent to "is 3 odd?", which is in turn equivalent to "is 2 even?", and so on down to 0. This example is mutual single recursion, and could easily be replaced by iteration. In this example, the mutually recursive calls are tail calls, and tail call optimization would be necessary to execute in constant stack space. In C, this would take "O"("n") stack space, unless rewritten to use jumps instead of calls.