Even with a fold-based representation of numbers, and pred/equal/subtraction, some recursive functions are going to be out of our reach.
Need a general method, where f(n) doesn't just depend on f(n-1) or (f(n-1),f(n-2),..). Fibonacci can be done without Y.
Ackermann function would need Y, but surely we can find some simpler demonstration?
How to do with recursion with omega.
fixed point combinators