Did you intend to note that "this sentence is either true or false" is a true sentence (for most methods of evaluation) that can't be evaluated by Yvain's fairly straightforward approach? Because that's definitely interesting (thanks Jack).

Just not messing with recursion, in general, is a fairly old solution and not very satisfying. I blame Yvain's writing ability for leading 9 people astray :D