What is the solution to the following recurrence relation with square root: $T(n)=T (\sqrt{n}) + 1$?

We have a recurrence that is ostensibly over the integers. But if $n$ is an integer, then $\sqrt{n}$ is not necessarily an integer. One way of getting an informal answer is to imagine that we start with an integer $n$ of the form $2^{2^m}$. Then $\sqrt{n}=2^{2^{m-1}}$. (To find the square root, we divide the exponent by $2$.)

So going up from $2^{2^0}$ to $2^{2^m}$, we have incremented $T$ by $m$. If we start with $T(2)=0$, then $$T\left(2^{2^m}\right)=m.$$ If $T(2)$ has some other value $a$, then $T\left(2^{2^m}\right)=a+m$. Note that $m=\log_2\left(\log_2\left(2^{2^m}\right)\right).$ So for this value of $n$, and $T(2)=0$, we have $T(n)=\log_2(\log_2(n))$. If $T(2)=a$, just add $a$.

Remark: The above calculation can be carried out in basically the same way if we assume that $T(n)=T(\lfloor\sqrt{n}\rfloor)+1$. The conclusion is that for large $n$, $T(n)$ behaves like $\lg\lg n$. And $\lg\lg n$ grows glacially slowly.

We shall find functions $x\mapsto T(x)$, defined for all real $x>1$, that satisfy the given recurrence relation.

Replace the unknown function $T$ by $$g(\alpha):=T\bigl(\exp(2^\alpha)\bigr)\qquad(-\infty<\alpha<\infty)\ .$$ Then, according to the recurrence relation for $T$, the function $g$ satisfies $$g(\alpha)=T\bigl(\sqrt{\exp(2^\alpha)}\bigr)+1=T\bigl(\exp(2^{\alpha-1})\bigr)+1=g(\alpha-1)+1\ ,$$ or $$f(\alpha):=g(\alpha)-\alpha=g(\alpha-1)-(\alpha-1)=f(\alpha-1)\qquad(\alpha\in{\mathbb R})\ .$$ This shows that $$g(\alpha)=\alpha +f(\alpha)\ ,$$ where now $f$ is an arbitrary function of period $1$.

In order to return to the variable $x$ we have to solve the equation $\exp(2^\alpha)=x$ for $\alpha$ and obtain $\alpha={\log\log x\over\log 2}$. As the steps leading to $g$ can be reversed, it follows that $$T(x)=g\Bigl({\log\log x\over\log 2}\Bigr)={\log\log x\over\log 2}+ f\Bigl({\log\log x\over\log 2}\Bigr)\qquad(x>1)$$ is the general solution of our problem.