I think there is a way to write a recurrence relation by the following reasoning: we are counting the permutations of $\left\{1 , \ldots , n\right\}$ which decomposition in cycles contains only cycles having at least $3$ elements. Let ${X}_{n}$ be that number. We can start with ${X}_{1} = {X}_{2} = 0$ and ${X}_{3} = 2$. Conventionally, we take ${X}_{0} = 1$.
Let $n \geqslant 3$. We choose $k \geqslant 2$ elements in $\left\{1 , \ldots , n-1\right\}$ to form a cycle with the element $n$. There are $\binom{n-1}{k}$ ways to find these elements and there are $k !$ ways to align them in a row to build the cycle with element $n$. For the remaining $n-k-1$ elements, we choose one of the
${X}_{n-k-1}$ valid permutations. Hence we obtain the relation
\begin{equation}
{X}_{n} = \sum _{k = 2}^{n-1} \binom{n-1}{k} \ k ! \ {X}_{n-k-1}
= (n-1)!\sum _{k = 2}^{n-1} \frac{{X}_{n-k-1}}{(n-k-1)!}
\end{equation}
This easily entails the relation $X_n = (n-1)X_{n-1} + (n-1)(n-2) X_{n-3}$.
Note that this order 3 relation can be shown directly by another way of counting the permutations:
Second reasoning We can separate the valid permutations between the permutations for which the number $n$ belongs to a 3-cycle (there are $(n-1)(n-2) X_{n-3}$ of them because there are $(n-1)(n-2)/2$ ways of choosing the two other elements of the 3-cycle and each choice gives two possible cycles) and the permutations for which the number $n$ belongs to a larger cycle. Those are obtained by inserting the number $n$ in one of the cycles of a valid permutation of the $n-1$ first elements. For a given such permutation, there are exactly $n-1$ places where to insert the $n$-th element, between one of the $n-1$ first numbers and its successor in a cycle. Hence there are $(n-1)X_{n-1}$ such permutations. This proves the order 3 relation.
Clearly, the same reasoning shows that if we generalize and we count instead the number $Y_n$ of permutations of $\{1,\cdots, n\}$ where all the cycles have a length $\ge p$, then we have the relation
\begin{equation}
Y_n = (n-1) Y_{n-1} + (n-1)\cdots (n-p+1) Y_{n-p}
\end{equation}
