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