That's co-recursion, rather than strict recursion. It's plausible that a compiler might catch the tail recursion case but ignore non-recursive and co-recursive

That's co-recursion, rather than strict recursion. It's plausible that a compiler might catch the tail recursion case but ignore non-recursive and co-recursive tail calls. Consider: def even(x, useless, arguments); return x == 0 or odd(abs(x) - 1) def odd(x): return x == 1 or even(abs(x) - 1, 6, 9) There are two more formal parameters to even(), which means the stack frame when calling even from odd() includes two more actual parameters. If the compiler follows the usual stack management approach of having the caller allocate and release space for actual parameters, this means the caller has to be aware that the stack space for odd's actual parameters is larger than the size needed for its formal parameters. If odd() is tail calling odd(), there's no difference in actual parameter space, and so the caller can be ignorant of it. It's a minor enough difference that any compiler implementing TCO should handle it anyway (just keep track of the maximum parameter size required in a function's tail call tree, and have the caller allocate and free enough space, or have the cleanup of actual parameters performed by callee) but big enough that a toy or experimental compiler, or one in which TCO is being slowly added, might just do the simple case only.