Part I. Let us first check that each of the functions above really satisfies the given functional equation. If $f(n)=n+1$ for all $n$, then we have
$$n^{2}+4 f(n)=n^{2}+4 n+4=(n+2)^{2}=f(n+1)^{2}=f(f(n))^{2} .$$
If $f(n)=n+1$ for $n>-a$ and $f(n)=-n+1$ otherwise, then we have the same identity for $n>-a$ and
$$n^{2}+4 f(n)=n^{2}-4 n+4=(2-n)^{2}=f(1-n)^{2}=f(f(n))^{2}$$
otherwise. The same applies to the third solution (with $a=0$ ), where in addition one has
$$0^{2}+4 f(0)=0=f(f(0))^{2}$$
Part II. It remains to prove that these are really the only functions that satisfy our functional equation. We do so in three steps:
Step 1: We prove that $f(n)=n+1$ for $n>0$.
Consider the sequence ($a_{k}$) given by $a_{k}=f^{k}(1)$ for $k \geqslant 0$. Setting $n=a_{k}$ in (1), we get
$$a_{k}^{2}+4 a_{k+1}=a_{k+2}^{2}$$
Of course, $a_{0}=1$ by definition. Since $a_{2}^{2}=1+4 a_{1}$ is odd, $a_{2}$ has to be odd as well, so we set $a_{2}=2 r+1$ for some $r \in \mathbb{Z}$. Then $a_{1}=r^{2}+r$ and consequently
$$a_{3}^{2}=a_{1}^{2}+4 a_{2}=(r^{2}+r)^{2}+8 r+4$$
Since $8 r+4 \neq 0, a_{3}^{2} \neq(r^{2}+r)^{2}$, so the difference between $a_{3}^{2}$ and $(r^{2}+r)^{2}$ is at least the distance from $(r^{2}+r)^{2}$ to the nearest even square (since $8 r+4$ and $r^{2}+r$ are both even). This implies that
$$|8 r+4|=|a_{3}^{2}-(r^{2}+r)^{2}| \geqslant(r^{2}+r)^{2}-(r^{2}+r-2)^{2}=4(r^{2}+r-1)$$
(for $r=0$ and $r=-1$, the estimate is trivial, but this does not matter). Therefore, we have
$$4 r^{2} \leqslant|8 r+4|-4 r+4$$
If $|r| \geqslant 4$, then
$$4 r^{2} \geqslant 16|r| \geqslant 12|r|+16>8|r|+4+4|r|+4 \geqslant|8 r+4|-4 r+4$$
a contradiction. Thus $|r|<4$. Checking all possible remaining values of $r$, we find that $(r^{2}+r)^{2}+8 r+4$ is only a square in three cases: $r=-3, r=0$ and $r=1$. Let us now distinguish these three cases:
- $r=-3$, thus $a_{1}=6$ and $a_{2}=-5$. For each $k \geqslant 1$, we have
$$a_{k+2}= \pm \sqrt{a_{k}^{2}+4 a_{k+1}}$$
and the sign needs to be chosen in such a way that $a_{k+1}^{2}+4 a_{k+2}$ is again a square. This yields $a_{3}=-4, a_{4}=-3, a_{5}=-2, a_{6}=-1, a_{7}=0, a_{8}=1, a_{9}=2$. At this point we have reached a contradiction, since $f(1)=f(a_{0})=a_{1}=6$ and at the same time $f(1)=f(a_{8})=a_{9}=2$.
- $r=0$, thus $a_{1}=0$ and $a_{2}=1$. Then $a_{3}^{2}=a_{1}^{2}+4 a_{2}=4$, so $a_{3}= \pm 2$. This, however, is a contradiction again, since it gives us $f(1)=f(a_{0})=a_{1}=0$ and at the same time $f(1)=f(a_{2})=a_{3}= \pm 2$.
- $r=1$, thus $a_{1}=2$ and $a_{2}=3$. We prove by induction that $a_{k}=k+1$ for all $k \geqslant 0$ in this case, which we already know for $k \leqslant 2$ now. For the induction step, assume that $a_{k-1}=k$ and $a_{k}=k+1$. Then
$$a_{k+1}^{2}=a_{k-1}^{2}+4 a_{k}=k^{2}+4 k+4=(k+2)^{2}$$
so $a_{k+1}= \pm(k+2)$. If $a_{k+1}=-(k+2)$, then
$$a_{k+2}^{2}=a_{k}^{2}+4 a_{k+1}=(k+1)^{2}-4 k-8=k^{2}-2 k-7=(k-1)^{2}-8$$
The latter can only be a square if $k=4$ (since 1 and 9 are the only two squares whose difference is 8 ). Then, however, $a_{4}=5, a_{5}=-6$ and $a_{6}= \pm 1$, so
$$a_{7}^{2}=a_{5}^{2}+4 a_{6}=36 \pm 4$$
but neither 32 nor 40 is a perfect square. Thus $a_{k+1}=k+2$, which completes our induction. This also means that $f(n)=f(a_{n-1})=a_{n}=n+1$ for all $n \geqslant 1$.

Step 2: We prove that either $f(0)=1$, or $f(0)=0$ and $f(n) \neq 0$ for $n \neq 0$.
Set $n=0$ in (1) to get
$$4 f(0)=f(f(0))^{2}$$
This means that $f(0) \geqslant 0$. If $f(0)=0$, then $f(n) \neq 0$ for all $n \neq 0$, since we would otherwise have
$$n^{2}=n^{2}+4 f(n)=f(f(n))^{2}=f(0)^{2}=0$$
If $f(0)>0$, then we know that $f(f(0))=f(0)+1$ from the first step, so
$$4 f(0)=(f(0)+1)^{2}$$
which yields $f(0)=1$.

Step 3: We discuss the values of $f(n)$ for $n<0$.
Lemma. For every $n \geqslant 1$, we have $f(-n)=-n+1$ or $f(-n)=n+1$. Moreover, if $f(-n)= -n+1$ for some $n \geqslant 1$, then also $f(-n+1)=-n+2$.
Proof. We prove this statement by strong induction on $n$. For $n=1$, we get
$$1+4 f(-1)=f(f(-1))^{2}$$
Thus $f(-1)$ needs to be nonnegative. If $f(-1)=0$, then $f(f(-1))=f(0)= \pm 1$, so $f(0)=1$ (by our second step). Otherwise, we know that $f(f(-1))=f(-1)+1$, so
$$1+4 f(-1)=(f(-1)+1)^{2}$$
which yields $f(-1)=2$ and thus establishes the base case. For the induction step, we consider two cases:
- If $f(-n) \leqslant-n$, then
$$f(f(-n))^{2}=(-n)^{2}+4 f(-n) \leqslant n^{2}-4 n<(n-2)^{2}$$
so $|f(f(-n))| \leqslant n-3$ (for $n=2$, this case cannot even occur). If $f(f(-n)) \geqslant 0$, then we already know from the first two steps that $f(f(f(-n)))=f(f(-n))+1$, unless perhaps if $f(0)=0$ and $f(f(-n))=0$. However, the latter would imply $f(-n)=0$ (as shown in Step 2) and thus $n=0$, which is impossible. If $f(f(-n))<0$, we can apply the induction hypothesis to $f(f(-n))$. In either case, $f(f(f(-n)))= \pm f(f(-n))+1$. Therefore,
$$f(-n)^{2}+4 f(f(-n))=f(f(f(-n)))^{2}=( \pm f(f(-n))+1)^{2}$$
which gives us
$$\begin{aligned} n^{2} & \leqslant f(-n)^{2}=( \pm f(f(-n))+1)^{2}-4 f(f(-n)) \leqslant f(f(-n))^{2}+6|f(f(-n))|+1 \\ & \leqslant(n-3)^{2}+6(n-3)+1=n^{2}-8 \end{aligned}$$
a contradiction.
- Thus, we are left with the case that $f(-n)>-n$. Now we argue as in the previous case: if $f(-n) \geqslant 0$, then $f(f(-n))=f(-n)+1$ by the first two steps, since $f(0)=0$ and $f(-n)=0$ would imply $n=0$ (as seen in Step 2) and is thus impossible. If $f(-n)<0$, we can apply the induction hypothesis, so in any case we can infer that $f(f(-n))= \pm f(-n)+1$. We obtain
$$(-n)^{2}+4 f(-n)=( \pm f(-n)+1)^{2}$$
so either
$$n^{2}=f(-n)^{2}-2 f(-n)+1=(f(-n)-1)^{2}$$
which gives us $f(-n)= \pm n+1$, or
$$n^{2}=f(-n)^{2}-6 f(-n)+1=(f(-n)-3)^{2}-8 .$$
Since 1 and 9 are the only perfect squares whose difference is 8 , we must have $n=1$, which we have already considered.
Finally, suppose that $f(-n)=-n+1$ for some $n \geqslant 2$. Then
$$f(-n+1)^{2}=f(f(-n))^{2}=(-n)^{2}+4 f(-n)=(n-2)^{2}$$
so $f(-n+1)= \pm(n-2)$. However, we already know that $f(-n+1)=-n+2$ or $f(-n+1)=n$, so $f(-n+1)=-n+2$.
Combining everything we know, we find the solutions as stated in the answer:
- One solution is given by $f(n)=n+1$ for all $n$.
- If $f(n)$ is not always equal to $n+1$, then there is a largest integer $m$ (which cannot be positive) for which this is not the case. In view of the lemma that we proved, we must then have $f(n)=-n+1$ for any integer $n<m$. If $m=-a<0$, we obtain $f(n)=-n+1$ for $n \leqslant-a$ (and $f(n)=n+1$ otherwise). If $m=0$, we have the additional possibility that $f(0)=0, f(n)=-n+1$ for negative $n$ and $f(n)=n+1$ for positive $n$.

Let us provide an alternative proof for Part II, which also proceeds in several steps.
Step 1. Let $a$ be an arbitrary integer and $b=f(a)$. We first concentrate on the case where $|a|$ is sufficiently large.
1. If $b=0$, then (1) applied to $a$ yields $a^{2}=f(f(a))^{2}$, thus
$$\begin{equation*} f(a)=0 \quad \Rightarrow \quad a= \pm f(0) \tag{2} \end{equation*}$$
From now on, we set $D=|f(0)|$. Throughout Step 1, we will assume that $a \notin\{-D, 0, D\}$, thus $b \neq 0$.
2. From (1), noticing that $f(f(a))$ and $a$ have the same parity, we get
$$0 \neq 4|b|=|f(f(a))^{2}-a^{2}| \geqslant a^{2}-(|a|-2)^{2}=4|a|-4$$
Hence we have
$$\begin{equation*} |b|=|f(a)| \geqslant|a|-1 \quad \text{ for } a \notin\{-D, 0, D\} . \tag{3} \end{equation*}$$
For the rest of Step 1, we also assume that $|a| \geqslant E=\max \{D+2,10\}$. Then by (3) we have $|b| \geqslant D+1$ and thus $|f(b)| \geqslant D$.
3. Set $c=f(b)$; by (3), we have $|c| \geqslant|b|-1$. Thus (1) yields
$$a^{2}+4 b=c^{2} \geqslant(|b|-1)^{2}$$
which implies
$$a^{2} \geqslant(|b|-1)^{2}-4|b|=(|b|-3)^{2}-8>(|b|-4)^{2}$$
because $|b| \geqslant|a|-1 \geqslant 9$. Thus (3) can be refined to
$$|a|+3 \geqslant|f(a)| \geqslant|a|-1 \quad \text{ for }|a| \geqslant E .$$
Now, from $c^{2}=a^{2}+4 b$ with $|b| \in[|a|-1,|a|+3]$ we get $c^{2}=(a \pm 2)^{2}+d$, where $d \in\{-16,-12,-8,-4,0,4,8\}$. Since $|a \pm 2| \geqslant 8$, this can happen only if $c^{2}=(a \pm 2)^{2}$, which in turn yields $b= \pm a+1$. To summarise,
$$\begin{equation*} f(a)=1 \pm a \quad \text{ for }|a| \geqslant E \tag{4} \end{equation*}$$
We have shown that, with at most finitely many exceptions, $f(a)=1 \pm a$. Thus it will be convenient for our second step to introduce the sets
$$Z_{+}=\{a \in \mathbb{Z}: f(a)=a+1\}, \quad Z_{-}=\{a \in \mathbb{Z}: f(a)=1-a\}, \quad \text{ and } \quad Z_{0}=\mathbb{Z} \backslash\left(Z_{+} \cup Z_{-}\right) .$$
Step 2. Now we investigate the structure of the sets $Z_{+}, Z_{-}$, and $Z_{0}$.
4. Note that $f(E+1)=1 \pm(E+1)$. If $f(E+1)=E+2$, then $E+1 \in Z_{+}$. Otherwise we have $f(1+E)=-E$; then the original equation (1) with $n=E+1$ gives us $(E-1)^{2}=f(-E)^{2}$, so $f(-E)= \pm(E-1)$. By (4) this may happen only if $f(-E)=1-E$, so in this case $-E \in Z_{+}$. In any case we find that $Z_{+} \neq \varnothing$.
5. Now take any $a \in Z_{+}$. We claim that every integer $x \geqslant a$ also lies in $Z_{+}$. We proceed by induction on $x$, the base case $x=a$ being covered by our assumption. For the induction step, assume that $f(x-1)=x$ and plug $n=x-1$ into ( 1 ). We get $f(x)^{2}=(x+1)^{2}$, so either $f(x)=x+1$ or $f(x)=-(x+1)$.
Assume that $f(x)=-(x+1)$ and $x \neq-1$, since otherwise we already have $f(x)=x+1$. Plugging $n=x$ into (1), we obtain $f(-x-1)^{2}=(x-2)^{2}-8$, which may happen only if $x-2= \pm 3$ and $f(-x-1)= \pm 1$. Plugging $n=-x-1$ into (1), we get $f( \pm 1)^{2}=(x+1)^{2} \pm 4$, which in turn may happen only if $x+1 \in\{-2,0,2\}$.
Thus $x \in\{-1,5\}$ and at the same time $x \in\{-3,-1,1\}$, which gives us $x=-1$. Since this has already been excluded, we must have $f(x)=x+1$, which completes our induction.
6. Now we know that either $Z_{+}=\mathbb{Z}$ (if $Z_{+}$is not bounded below), or $Z_{+}=\left\{a \in \mathbb{Z}: a \geqslant a_{0}\right\}$, where $a_{0}$ is the smallest element of $Z_{+}$. In the former case, $f(n)=n+1$ for all $n \in \mathbb{Z}$, which is our first solution. So we assume in the following that $Z_{+}$is bounded below and has a smallest element $a_{0}$.
If $Z_{0}=\varnothing$, then we have $f(x)=x+1$ for $x \geqslant a_{0}$ and $f(x)=1-x$ for $x<a_{0}$. In particular, $f(0)=1$ in any case, so $0 \in Z_{+}$and thus $a_{0} \leqslant 0$. Thus we end up with the second solution listed in the answer. It remains to consider the case where $Z_{0} \neq \varnothing$.
7. Assume that there exists some $a \in Z_{0}$ with $b=f(a) \notin Z_{0}$, so that $f(b)=1 \pm b$. Then we have $a^{2}+4 b=(1 \pm b)^{2}$, so either $a^{2}=(b-1)^{2}$ or $a^{2}=(b-3)^{2}-8$. In the former case we have $b=1 \pm a$, which is impossible by our choice of $a$. So we get $a^{2}=(b-3)^{2}-8$, which implies $f(b)=1-b$ and $|a|=1,|b-3|=3$.
If $b=0$, then we have $f(b)=1$, so $b \in Z_{+}$and therefore $a_{0} \leqslant 0$; hence $a=-1$. But then $f(a)=0=a+1$, so $a \in Z_{+}$, which is impossible.
If $b=6$, then we have $f(6)=-5$, so $f(-5)^{2}=16$ and $f(-5) \in\{-4,4\}$. Then $f(f(-5))^{2}= 25+4 f(-5) \in\{9,41\}$, so $f(-5)=-4$ and $-5 \in Z_{+}$. This implies $a_{0} \leqslant-5$, which contradicts our assumption that $\pm 1=a \notin Z_{+}$.
8. Thus we have shown that $f\left(Z_{0}\right) \subseteq Z_{0}$, and $Z_{0}$ is finite. Take any element $c \in Z_{0}$, and consider the sequence defined by $c_{i}=f^{i}(c)$. All elements of the sequence $\left(c_{i}\right)$ lie in $Z_{0}$, hence it is bounded. Choose an index $k$ for which $\left|c_{k}\right|$ is maximal, so that in particular $\left|c_{k+1}\right| \leqslant\left|c_{k}\right|$ and $\left|c_{k+2}\right| \leqslant\left|c_{k}\right|$. Our functional equation (1) yields
$$\left(\left|c_{k}\right|-2\right)^{2}-4=\left|c_{k}\right|^{2}-4\left|c_{k}\right| \leqslant c_{k}^{2}+4 c_{k+1}=c_{k+2}^{2}$$
Since $c_{k}$ and $c_{k+2}$ have the same parity and $\left|c_{k+2}\right| \leqslant\left|c_{k}\right|$, this leaves us with three possibilities: $\left|c_{k+2}\right|=\left|c_{k}\right|,\left|c_{k+2}\right|=\left|c_{k}\right|-2$, and $\left|c_{k}\right|-2= \pm 2, c_{k+2}=0$.
If $\left|c_{k+2}\right|=\left|c_{k}\right|-2$, then $f\left(c_{k}\right)=c_{k+1}=1-\left|c_{k}\right|$, which means that $c_{k} \in Z_{-}$or $c_{k} \in Z_{+}$, and we reach a contradiction.
If $\left|c_{k+2}\right|=\left|c_{k}\right|$, then $c_{k+1}=0$, thus $c_{k+3}^{2}=4 c_{k+2}$. So either $c_{k+3} \neq 0$ or (by maximality of $\left.\left|c_{k+2}\right|=\left|c_{k}\right|\right) c_{i}=0$ for all $i$. In the former case, we can repeat the entire argument
with $c_{k+2}$ in the place of $c_{k}$. Now $\left|c_{k+4}\right|=\left|c_{k+2}\right|$ is not possible any more since $c_{k+3} \neq 0$, leaving us with the only possibility $\left|c_{k}\right|-2=\left|c_{k+2}\right|-2= \pm 2$.
Thus we know now that either all $c_{i}$ are equal to 0 , or $\left|c_{k}\right|=4$. If $c_{k}= \pm 4$, then either $c_{k+1}=0$ and $\left|c_{k+2}\right|=\left|c_{k}\right|=4$, or $c_{k+2}=0$ and $c_{k+1}=-4$. From this point onwards, all elements of the sequence are either 0 or $\pm 4$.
Let $c_{r}$ be the last element of the sequence that is not equal to 0 or $\pm 4$ (if such an element exists). Then $c_{r+1}, c_{r+2} \in\{-4,0,4\}$, so
$$c_{r}^{2}=c_{r+2}^{2}-4 c_{r+1} \in\{-16,0,16,32\}$$
which gives us a contradiction. Thus all elements of the sequence are equal to 0 or $\pm 4$, and since the choice of $c_{0}=c$ was arbitrary, $Z_{0} \subseteq\{-4,0,4\}$.
9. Finally, we show that $4 \notin Z_{0}$ and $-4 \notin Z_{0}$. Suppose that $4 \in Z_{0}$. Then in particular $a_{0}$ (the smallest element of $Z_{+}$) cannot be less than 4 , since this would imply $4 \in Z_{+}$. So $-3 \in Z_{-}$, which means that $f(-3)=4$. Then $25=(-3)^{2}+4 f(-3)=f(f(-3))^{2}=f(4)^{2}$, so $f(4)= \pm 5 \notin Z_{0}$, and we reach a contradiction.
Suppose that $-4 \in Z_{0}$. The only possible values for $f(-4)$ that are left are 0 and -4 . Note that $4 f(0)=f(f(0))^{2}$, so $f(0) \geqslant 0$. If $f(-4)=0$, then we get $16=(-4)^{2}+0=f(0)^{2}$, thus $f(0)=4$. But then $f(f(-4)) \notin Z_{0}$, which is impossible. Thus $f(-4)=-4$, which gives us $0=(-4)^{2}+4 f(-4)=f(f(-4))^{2}=16$, and this is clearly absurd.
Now we are left with $Z_{0}=\{0\}$ and $f(0)=0$ as the only possibility. If $1 \in Z_{-}$, then $f(1)=0$, so $1=1^{2}+4 f(1)=f(f(1))^{2}=f(0)^{2}=0$, which is another contradiction. Thus $1 \in Z_{+}$, meaning that $a_{0} \leqslant 1$. On the other hand, $a_{0} \leqslant 0$ would imply $0 \in Z_{+}$, so we can only have $a_{0}=1$. Thus $Z_{+}$comprises all positive integers, and $Z_{-}$comprises all negative integers. This gives us the third solution.