> It seems likely that any recursive sequence with a single initial condition - specifically, you have an x0, and then every other term f(x) is some function of only the term before it - should be able to get translated into explicit form every time.
Not at all. As an analogue, do you expect any first-order ODE with an initial condition should have an "explicit" solution formula? The scope of *any* recursion and *any* ODE is extremely broad. If you had been speaking about *linear* recursions or *linear* differential equations, that's one thing, but when you allow anything at all, then nonlinear possibilities are going to make things extremely difficult when the goal is explicit solution formulas.