Suppose $S_R$ – is the set of all total recursive bijections on $\mathbb{N}$. It is not hard to see that this set forms a group with respect to composition, and that $|S_R| = \aleph_0$. Is $S_R$ finitely generated?
The group $S_R$ contains the group $S_\infty$ (the group of finitely based bijections) as its subgroup, which is infinitely generated. However, there exists $S_\infty < H \leq S_R$, such that $H$ is finitely generated. The $H$ can be described as $\langle (01), f \rangle$, where $f$ is defined by formula:
$$f(x) = \begin{cases} 0 & \quad x = 0 \\ 2 & \quad x = 1 \\ x + 2 & \quad x \geq 2 \text{ and is even} \\ x – 2 & \quad x \geq 2 \text{ and is odd} \end{cases}$$
Indeed, $\forall x = 2n+1$ $(0x)=(01)f^{n}$ and $\forall x = 2n$ $(0x)=(01)f^{-n}$. Hovever, this does not give us the answer to the question as $H$ is most likely a proper subgroup of $S_R$ (though, i do not know for sure).
Best Answer
I initially only answered the question whether $H\neq S_R$, where I just confirm I negative answer, and said I think $\mathrm{Sym}_{\mathrm{Rec}}(\mathbf{N})$ is known not to be finitely generated. I've added a proof of this fact as an edit, below.
Original answer:
Your group is easier to describe using $\mathbf{Z}$ than $\mathbf{N}$ (using a recursive bijection between the two). Namely, under this isomorphism it corresponds to $H_1=\langle S_\infty(\mathbf{Z}),f_0\rangle$, and by $f_0$ defined by $f_0(n)=n+1$ for $n\neq 0,-1$, $f(0)=0$, $f(-1)=1$ (infinite cycle with fixed point). This group can be defined "implicitly", namely as the group of permutations of $\mathbf{Z}$ that eventually coincide with a translation. It's also more simply described as $\langle S_\infty(\mathbf{Z}),f_1\rangle$, with $f_1(n)=n+1$.
It's quite clear that $H_1$ is not the whole group of recursive permutations of $\mathbf{Z}$. Indeed, your $f$, viewed as permutation of $\mathbf{Z}$ (fixing negative integers), is not in $H_1$.
(Also there's a unique homomorphism $H_1\to\mathbf{Z}$ mapping $f_1$ to $1$, while $\mathrm{Sym}_{\mathrm{Rec}}(\mathbf{Z})$ can be shown t be a perfect group. Indeed it was proved by C. Kent (1962, link at AMS site) that $\mathrm{Sym}_{\mathrm{Rec}}(\mathbf{Z})$ has only 4 normal subgroups (similarly as in the Onofri/Schreier-Ulam theorem): the whole, the trivial subgroup, the finitary subgroup, and the subgroup of index 2 therein).
Edit: It took me a few hours to reconstitute the argument of infinite generation, which was enough for a grumpy user to downvote.
Lemma There is no computable map $f:\mathbf{N}^2\to \mathbf{N}$ such that $n\mapsto f(n,-)=:f_n$ is a surjection of $\mathbf{N}$ onto $S_R$.
Proof: assume so. Let $u(n,m)=u_n(m)$ be the supremum of $f_n$ on $[0,m]$. So $(m,n)\mapsto u(m,n)$ is computable. Let $u$ be a computable increasing function such that $u\gg u_n$ for all $n$ (it exists by an easy diagonal argument, namely $u=\sum \mathbf{1}_{[n,\infty[}u_n)$). Let $q$ be the permutation exchanging $n$ and $2u(n)$ for every odd $n$, and fixing other elements. Then it is computable, and cannot be among the $f_n$.
Corollary $S_R$ is not finitely generated.
Proof: otherwise, it's generated by some finite subset $S$. Then using the surjective map $p:F_S\to S_R$ and using a computable bijection $q:\mathbf{N}\to F_S$ we get the map $(n,m)\mapsto q(n)m$ which is computable and contradicts the lemma.