Is there a recurrence relation which has no closed formula?

This may be kind of weak, but in a certain sense, Liouville's theorem guarantees there is no closed formula for $a_0 =0$ and $a_n = a_{n-1} + \int_{n-1}^n e^{-x^2} \text{d}x$.

Here is a remark I put in a paper [1, p. 5828] of mine, which I got from an anonymous referee of that paper:

We may resonably interpret "having closed form" as "being differentiably algebraic". According to Eremenko, the integer iterates of a polynomial $M(x)$ are uniformly differentiably algebraic (= satisfy the same algebraic differential equation with constant coefficients) iff $M$ is conjugate (by a linear function) to a monomial, a Chebyshev polynomial, or the negative of a Chebyshev polynomial. See [2, p. 663]. In case $M(x) = x^2+c$, this means precisely $c=0$ or $c=-2$.

So in the case $M(x) = x^2+1$ mentioned by the O.P., the iteration does not have closed form in this sense.

Note that Erimenko is a member here, so he may able to provide more information!

[1] Edgar, G. A., Fractional iteration of series and transseries, Trans. Am. Math. Soc. 365, No. 11, 5805-5832 (2013). ZBL1283.30001.

[2] Rubel, Lee A., Some research problems about algebraic differential equations. II, Ill. J. Math. 36, No. 4, 659-680 (1992). ZBL0768.34003.