Consider a function $w(i)$, $i \in \mathbb{N}$, defined recursively by:


$w(0)=w(1)=1$, and


$w(i)={i}^{n}-\sum\_{j=1}^{i-1}{i \choose j}w(j)$ for $i>1$.


Is it possible to write $w(i)$ out explicitly as a function of $i$ (i.e., with only $i$ on the right hand side), for $i>1$ ?


In general, given a recursively defined total computable function say, $f(n)$, is it always possible, in principle, to write out $f(n)$ explicitly as a function of $n$, for $n$ large enough? I suspect it's impossible. If so, what is the real reason that prevents us from doing so? 


Another well known example that comes to my mind is:


$f(0)=f(1)=c$, and 


$f(i)=5f(i-1)(1-f(i-1))$ 


where we can choose some value of $c \in (0,1)$ so that the trajectory of $f(i)$ becomes chaotic in $(0,1)$. If we could really express any recursively defined total computable function explicitly, then we could write out the chaotic trajectory in a finite, flat and non-dynamic formula, which seems strange to me. (or can we?) 




---


**Edit**: Thank you very much for all the answers. They are really helpful. 


@Joel: Is the recursive formation essential when the resulting recursive function doesn't grow faster than it's component functions ${g}\_{i}$ (in your notation)? i.e., is it true that given ${g}\_{i}$ and recursive function $f$ defined on them, as long as $f$ doesn't grow faster than the fastest of ${g}\_{i}$, the recursive formation can be dispensed with?


@Carl: By ***"...it is not possible to come up with a completely explicit form for every computable function, in some fixed signature"*** , did you mean to write out the functions symbolically using finite, fixed set of symbols? In @Joel's interpretation, he didn't distinguish between we being able to symbolically write out exponential functions as, say ${2}^{n}$, and just taking the recursive function on multiplication as another "known" basic function ${g}\_{i}$. Of course, one may just dismiss ${2}^{n}$ as a "shorthand" for the whole recursive formation, but I do feel they are not quite the same ("${2}^{n}$" is closer to what I had in mind by "explicit". I'd like to know if the distinction makes any sense in any sense). 


Another question I have concerns about this "...***because then by enumerating all possible forms we would get a numbering ϕ as in the theorem***" But just because we can write a completely explicit form for each computable function doesn't mean we can enumerate these forms **effectively**, does it? If we can't, this does not contradict the theorem. Can you be more specific about this? Thanks! 



Explicit expression for recursively defined functions
The class of [primitive recursive functions](http://en.wikipedia.org/wiki/Primitive_recursive_functions) is the smallest class of functions containing the basic primitive recursive functions (zero, successor, projection) and closed under the two operations:


* composition: if $h$ and $g\_1,\ldots,g\_k$ are primitive recursive, so is the function $$\vec x\mapsto h(g\_1(\vec x),g\_2(\vec x),\ldots,g\_k(\vec x)).$$
* primitive recursion: if $h$ and $g$ are primitive recursive, then so is the function $f$ defined by $$f(0,\vec x)=h(\vec x),$$ $$f(n+1,\vec x)=g(n,\vec x, f(n,\vec x)).$$


This class is extremely robust and includes all of the functions that you mention in your question (but it falls short of the class of all Turing computable functions). 
I interpret your question as being about the extent to which we might hope to eliminate the recursion scheme, and still arrive at the same class of functions. 


One easy observation, of course, is that we cannot simply eliminate the recursion scheme as is and still get all primitive recursive functions. For example, even if we add addition and multiplication as basic functions, then the composition scheme will remain inside the class of polynomial functions. But we can easily define the exponential function $n\mapsto 2^n$ by recursion over that class, and this does not have polynomial growth. 


More generally, let us consider whether we might add finitely many additional, powerful primitive recursive functions $g\_1,\ldots,g\_k$ as basic, and then close only under composition. This interpretation of the question would be: can we arrange that this class is closed under definition by recursion? In other words, is every function definable by recursion using those functions and their compositions already expressible as a term in the language using only those functions (that is, as a composition)? 


The answer to this more general version of the question is still no. For any finitely many primitive recursive functions $g\_1,\ldots,g\_k$, the closure of it under composition is strictly smaller than the closure of it under composition and definition by recursion. Specifically, there will be a primitive recursive function $f$, defined by one or more recursions over those $g\_i$ and the usual basic functions, which has a higher growth rate than any individual term in those functions. This can be proved by using a high enough level function $A\_n$ of the [Ackermann function](http://en.wikipedia.org/wiki/Ackermann_function), because whenever a collection of functions is dominated by $A\_n$, then all terms in those functions are dominated by $A\_{n+1}$.


