If you take exponential with a base $a < e^{1/e}$ finding the iterative square root of $f(x)=a^x$ is not so difficult.

You can use one of the following formulas:

$$f^{[1/2]}(x)=\sum_{m=0}^{\infty} \binom {1/2}m \sum_{k=0}^m \binom mk (-1)^{m-k}\exp_a^{[k]}(x)$$

$$f^{[1/2]}(x)=\lim_{n\to\infty}\binom {1/2} n\sum_{k=0}^n\frac{x-n}{x-k}\binom nk(-1)^{n-k}\exp_a^{[k]}(x)$$

$$f^{[1/2]}(x)=\lim_{n\to\infty}\frac{\sum_{k=0}^{2n} \frac{(-1)^k \exp_a^{[k]}(x)}{(1/2-k)k!(2n-k)!}}{\sum_{k=0}^{2n} \frac{(-1)^k }{(1/2-k) k!(2n-k)!}}$$

$$f^{[1/2]}(x)=\lim_{n\to\infty} \log_a^{[n]}\left(\left(1-\left(\ln \left(\frac{W(-\ln a)}{-\ln a}\right)\right)^{1/2}\right)\frac{W(-\ln a)}{-\ln a}+\ln \left(\frac{W(-\ln a)}{-\ln a}\right)\exp_a^{[n]}(x)\right)$$

Here is a graph of an iterative square root of a function $f(x)=(\sqrt{2})^x$:

![alt text][1]


Regarding second part of the question, such specially constructed function is called [superfunction][2] or flow. For base $a \le e^{1/e}$ superfunction can be easily constructed from the above formulas by substituting variable instead of 1/2. Of course the superfunction is not unique but there are certain more "natural" solutions.

The question becomes more difficult when speaking about the base $a>e^{1/e}$. But in this case the superfunction can also be constructed, see [this article][3].


  [1]: https://i.sstatic.net/yTGW0.png
  [2]: http://en.wikipedia.org/wiki/Superfunction
  [3]: http://www.ils.uec.ac.jp/~dima/PAPERS/2009sqrt2.pdf