Can the Gaussian integers be covered by restricted recurrences? Relaxation of the second question here.
Let $a(n)$ be recurrence of the form $a(n)=f(n,a(n-1)\ldots(a(n-k))$
with fixed initial terms.
(Observe that it might depend on $n$).
$f$ may contain rational functions (if possible polynomials), radicals, $\Re$ and $\Im$.

Q1 Can $a(n)$ cover the Gaussian integers aka $\mathbb{Z}[i]$?
Q2 can $a(n)$ cover $a + b i$,$a,b \in \mathbb{Z},a,b >0$?

If floor() is allowed too, I believe the answer to Q2
is positive via the Cantor pairing and its inverse.
 A: If you allow radicals, then yes to Q1, and depending only on $a(n-1)$.  Let:
$$x=\Re( a(n-1))$$
$$y=\Im( a(n-1))$$
$$pos(r) = \frac{1}{2}\left( 1 + \frac{\sqrt{r^2}}{r}\right)$$
Note $pos(r)$ is 1 on positive reals and 0 on negative reals.  With this we can enumerate the Gaussian integers in progressively larger diamonds centered on the origin: 
\begin{align}
a(0) = &\ 0\\
a(n) = &\ a(n-1) + \\
&(-1 + i)\ pos(+x - 1/2)\ pos(+y -1/2)\  + \\
&(-1 - i)\ pos(-x + 1/2)\ pos(+y -1/2)\  + \\
&(+1 - i)\ pos(-x - 1/2)\ pos(-y + 1/2)\  + \\
&(+1 + i)\ pos(+x + 1/2)\ pos(-y - 1/2)\  + \\
&i\ pos(+x + 1/2)\ \left( pos( y + 1/2) - pos( y - 1/2)\right) 
\end{align}
A simple linear modification gives yes to Q2 also.
Even more explicitly:
Mathematica code:\begin{align}
\mathtt{pos[r\_] :=\ } & \mathtt{(1/2) (1 + Sqrt[r^2]/r);}\\
\mathtt{f[z\_] :=\ } & \mathtt{With[{x = Re[z], y = Im[z]}, z +}\\
\mathtt{    }&\mathtt{(-1 + I) pos[+x - 1/2] pos[+y - 1/2] +}\\
\mathtt{    }&\mathtt{(-1 - I) pos[-x + 1/2] pos[+y - 1/2] +}\\
\mathtt{    }&\mathtt{(+1 - I) pos[-x - 1/2] pos[-y + 1/2] +}\\
\mathtt{    }&\mathtt{(+1 + I) pos[+x + 1/2] pos[-y - 1/2] +}\\
\mathtt{    }&\mathtt{I\ pos[+x + 1/2] (pos[y + 1/2] - pos[y - 1/2])];}\\
\mathtt{NestList[} &\mathtt{f,0,13]}\\
\end{align}
Mathematica results, slightly formatted:
$\mathtt{\{0,\\
I,\ -1,\ -I,\ 1,\\
1 + I,\ 2 I,\ -1 + I,\ -2,\ -1 - I,\ -2 I,\ 1 - I,\ 2,\\ 
2 + I\}}$  
