The study of logic analyses recurrence on many levels. For instance, self-referential paradoxes are definitions of the same syntactic type as recurrence. In fact, the fact that f(x) = f(x) + 1 doesn't have a solution is very much the same reason as "this sentence is false". Tarski's undefinability of truth is a much deeper limit on the capability of recurrence in sufficiently strong formal systems.
Now, if you are looking for something with a little more concrete domains than syntaxes or truth values, there is always basic computer science with many functions defined by recurrence. There is the Ackermann function, the fast-growing hierarchy, and many other gems.
However, there is a really strong sense in which your question is poorly defined. All of these examples are in some sense combinatorial, and other examples like those in graph theory and higher data structures are naturally in the field. The liar paradox, for instance, can be seen as a particular combinatorial question on a tree with two nodes, and more widely, just as all mathematics can be seen interpreted as a sufficiently strong theory of arithmetic, the same goes for interpretations in combinatorics. So, although you can get examples from other fields, there is always going to be a sense where you can look at the example and find it's "just another combinatorial problem."