Is there a general method of turning an iterative function definition, for example $$f(x+1)= x^{f(x-1)}+f(x-1)^x$$ into a closed form equation? By closed form, I mean that I want an expression that does not grow arbitrarily large in length, and doesn't use symbols like $\sum$ or $\prod$ unless the number of steps for computing them is fixed. Essentially, it should not take a computer much longer to figure out $f(10000)$ that it should to figure out $f(500)$.
What about solving recursive functions in which $f(x)$ relies on both $f(x+1)$ and $f(x-1)$? Not necessarily those two, but any inputs both larger and smaller than $x$.
Look for "Hypergeometric Summation", "Summation in finite terms" and "Symbolic summation".
Read e.g. the chapter "Symbolic Summation" in Bona, Miklos: Handbook of Enumerative Combinatorics. Chapman and Hall/CRC 2015.
There is a theory or an algorithm of Michael Karr:
Karr, Michael: Summation in finite terms. J. Assoc. Comp. Mach. 28 (1981) (2)305-350
Karr, Michael: Theory of Summation in Finite Terms. J. Symbolic Computation 1 (1985) (3) 303-315
And there is a theory or an algorithm of Carsten Schneider:
Look for
Schneider Summation
and for
Schneider sums