I was searching for a smooth continuous concave function
$$f:R^{+}\times R^{+}\to R^{+}$$
so that
$$f(x+1,y)=\sqrt{y+f(x,y)}\quad\text{and}\quad f(0,y)=0.$$
But I couldn't find a general function, I found only expressions for some fixed $y$.
For $y=0$: $f(x,0)=0$.
And for $y=2$: $f(x,2)=2\cos(\frac{\pi}{2^{x+1}})$. This is actually the x-th member of sequence: $$ \sqrt{2} \\ \sqrt{2+\sqrt{2}} \\ \sqrt{2+\sqrt{2+\sqrt{2}}} \\ \dots $$
But I still don't have a formula for x-th member of the corresponding sequence for $y=1$:
$$ \sqrt{1} \\ \sqrt{1+\sqrt{1}} \\ \sqrt{1+\sqrt{1+\sqrt{1}}} \\ \dots $$
If you have the function for other $y$ or some ideas to find general function $f(x,y)$ it's welcome.
You add a bit more generality for the $y=2$ case.
Let $f(0,2) = a_0$ for some arbitrary real $a_0 \geq -2$. (Your solution is specific to $a_0 = 0$.)
Then:
If $a_0 = -2$ the solution is your $a_0 = 0$ solution, iwth x displaced by one.
If $-2 < a_0 < 2$, let $$r = \frac\pi 2\frac{1}{\cos^{-1}\left( \frac{a_0}{2}\right)} $$ and the solution is $$ a_x = 2 \cos \left( \frac{\pi}{r2^{x+1}} \right) $$ If $a_0 = 2$ the solution is trivially $\forall x: a_x = 2$.
And if $a_0 > 2$, let $$s = \frac {1} {\cosh^{-1}\left( \frac{a_0}{2}\right)} $$ and the solution is $$ a_x = 2 \cosh \left( \frac{1}{s2^{x}} \right) $$
For $y$ not satisfying $y^2 = y$ I suspect there is no non-trivial solution in terms of elementary functions.
By "non-trivial", that means to exclude the special values of $a_0$ for which there exists some finite positive $x$ and $n$ such that $$f(x,y;a_0) = f( x+n,y;a_0 ) $$ Such sequences can be described in terms of solutions to polynomial equations. The cases where $a_1 = a_0$ fall into this category of "trivial" solutions. For instance, if $y=3$, the solution $$f(x,3) = \frac{1+\sqrt{13}}{2} $$ for all $x$ satisfies the recurrence equation.