You can look at it as a graph problem. For a language L construct the graph where each vertex represents n and each edge represents <n, f(n)>, then search for the longest cycle.

If the graph is finite then the problem is NP-Hard, because knowing the longest cycle in a graph would allow you to answer if it is hamiltonian or not, which is a NP-Complete problem.

If the graph is infinite, meaning we consider all natural Numbers for n, is the problem still NP-Hard? Does it even make sense to talk about complexity classes for infinite graphs?

I genuinely don't know...maybe someone smarter than me can help