How do I find an upper bound on this recurrence

$f(n)=f(n-\sqrt{n})$

I believe $f(n)\in O(\sqrt{n})$

However I cannot seem to prove it, my intuition comes from the fact that we can remove $\sqrt{n}$ exactly $\sqrt{n}$ times, but if $n$ shrinks then does anything change?

For definiteness, let's assume that the recurrence is
$$
f(n) = \begin{cases}
f(\lfloor n-\sqrt{n} \rfloor) + 1 & n > 0 \\
0 & n = 0.
\end{cases}
$$
(We assume that the domain is the non-negative integers.)

Since $\lfloor n-\sqrt{n} \rfloor > n-\sqrt{n}-1$, we see that
$$
f(n) \geq \frac{n}{\sqrt{n}+1} = \Omega(\sqrt{n}).
$$
In the other direction, let us note that $f(n)$ is monotone and that
$$
f(n) \leq f(\lfloor n/2 \rfloor) + \frac{\lceil n/2 \rceil}{\sqrt{\lceil n/2 \rceil}}.
$$
This is because until the parameter gets down to $\lfloor n/2 \rfloor$ (or smaller), the decrease at every step is at least $\sqrt{\lceil n/2 \rceil}$. This shows that
$$
f(n) \leq f(\lfloor n/2 \rfloor) + \sqrt{\lceil n/2 \rceil} \leq f(\lfloor n/2 \rfloor) + \sqrt{n/2} + 1.
$$
Iterating this $\log_2 n+1$ times, we get
$$
\begin{align*}
f(n) &\leq f(\lfloor n/2 \rfloor) + \sqrt{n/2} + 1 \\ &\leq
f(\lfloor n/4 \rfloor) + \sqrt{n/2} + \sqrt{n/4} + 2 \\ &\leq \cdots \\ &\leq
f(0) + \sqrt{n/2} + \sqrt{n/4} + \cdots + \sqrt{n/2^{\log_2 n + 1}} + \log_2n + 1 \\ &\leq
\sqrt{n} \sum_{t=1}^\infty \frac{1}{\sqrt{2}^t} + O(\log n) \\ &= O(\sqrt{n}).
\end{align*}
$$
We conclude that $f(n) = \Theta(\sqrt{n})$.

StackExchange Computer Science Q#47171, answer score: 4