Let $a_n$ denote the number of permutations of odd order in $S_n$. This is sequence A000246 in OEIS. Then there is the recurrence relation on OEIS that $a_{2n} = (2n-1)a_{2n-1}$ and $a_{2n+1} = (2n+1)a_{2n}$, or equivalently $a_n = a_{n-1} + (n-1)(n-2)a_{n-2}$.
It seems like there should be a combinatorial proof for this result.
Since there isn't a simple recurrence for the number of partitions with odd parts, it doesn't seem like working on the level of partitions will work.
On
These permutations are precisely the ones that do not contain even cycles, giving the species
$$\mathfrak{P}(\mathfrak{C}_{=1}(\mathcal{Z}) + \mathfrak{C}_{=3}(\mathcal{Z}) + \mathfrak{C}_{=5}(\mathcal{Z}) + \mathfrak{C}_{=7}(\mathcal{Z}) + \cdots)$$
This yields the EGF
$$G(z) = \exp\left(\sum_{q\ge 1} \frac{z^q}{q} - \sum_{q\ge 1} \frac{z^{2q}}{2q}\right) \\ = \exp\log\frac{1}{1-z} \exp\left(- \frac{1}{2} \log\frac{1}{1-z^2}\right) \\ = \frac{\sqrt{1-z^2}}{1-z}.$$
Differentiate to obtain
$$G'(z) = \frac{\sqrt{1-z^2}}{1-z} \frac{1}{1-z} - \frac{\sqrt{1-z^2}}{1-z} \frac{z}{1-z^2} = G(z) \frac{1}{1-z^2}.$$
Extracting coefficients we find for $n\ge 2$
$$n! [z^n] G'(z) (1-z^2) = n! [z^n] G(z) \quad\text{or}\quad a_{n+1} - n! [z^{n-2}] G'(z) = a_n$$
which finally yields
$$a_{n+1} = a_n + n! \times \frac{a_{n-1}}{(n-2)!} \quad\text{or}\quad a_{n+1} = a_n + n (n-1) a_{n-1}$$
as desired.
For the second recurrence we start with the closed form from the EGF
$$n! \sum_{q=0}^{\lfloor n/2\rfloor} [z^{2q}] \sqrt{1-z^2} = n! \sum_{q=0}^{\lfloor n/2\rfloor} (-1)^q {1/2\choose q}.$$
Since $\lfloor (2n+1)/2\rfloor = \lfloor 2n/2\rfloor$ we have
$$a_{2n+1} = (2n+1) a_{2n}$$ by inspection.
The first recurrence now yields
$$a_{2n+1} = a_{2n} + 2n (2n-1) a_{2n-1} \quad\text{or}\quad (2n+1) a_{2n} = a_{2n} + 2n (2n-1) a_{2n-1}$$
and finally
$$2n a_{2n} = 2n (2n-1) a_{2n-1} \quad\text{or}\quad a_{2n} = (2n-1) a_{2n-1}.$$
$a_n-a_{n-1}$ is the number of odd order permutations in $S_n$ that move $1$. These permutations look like $(1\, i\,j\,\cdots)\cdots$ where the first cycle has odd length $\ge3$. The number of these is $(n-1)(n-2)t$ where $t$ is the number of odd order permutations $(1\, 2\,3\,\cdots)\cdots$. But these correspond to odd order permutations $(3\,\cdots)\cdots$ of the numbers $3$ to $n$. There are $a_{n-2}$ of these, and this proves your final recurrence.