In a class of mine, my professor said
The list of derangements of $\{a,b\}$ is $\{a,b\}$ and the list of derangements of $\{a,b,c\}$ is $\{\{a,b,c\},\{a,c,b\}\}$. Once you have all the derangements of an $n - 2$ element set and of an $n - 1$ element set, you can generate all the derangements of an $n$ element set by choosing one element $X$, forming all Type I derangements of the form $\{\{X,Y\}, \text{rest of cycles}\}$ and all Type II derangements by inserting $X$ into all possible derangements of the other elements in all possible ways.
I don't understand how this produces the derangements, and I'm not sure what is meant by "rest of cycles" and "inserting $X$ into all possible derangements of the other elements in all possible ways”.
Can someone describe to me how this algorithm works, through explanation, pseudocode, etc.?
Your quote is slightly wrong. The list of derangements of $(a,b)$ is $\{(b,a)\}$ and the list of derangements of $(a,b,c)$ is $\{(b,c,a), (c,a,b)\}$.
The recursive formula for derangements $d(n)$ is $d(n) = (n-1)(d(n-1) + d(n-2))$, with $d(0)=1$ and $d(1)=0$.
You can infer this recursion from moving the first element to some other location (that's the factor of $n{-}1$) and then either having that displaced value avoid the first spot (which looks like an $n{-}1$ derangement, $d(n-1)$ options) or go into the first spot (so the remaining elements must make an $n{-}2$ derangement, $d(n-2)$).
For $n=0..5$, this gives $d(n)=1,0,1,2,9,44$ - more terms at OEIS A000166
To illustrate how this works, let's look at a derangement of four elements $(a,b,c,d)$.
Move the first element to some other arbitrary position:
$(\cdot, \cdot, a,\cdot)$
Then if the displaced element $c$ avoids the first spot, we have the derangement of three elements, since $c$ is taking the role of $a$:
$\color{green}{(d, c, a, b)}$
$\color{green}{(b, d, a, c)}$
and if $c$ goes in the first spot, we just have the derangements of $(b,d)$
$\color{blue}{(c, d, a, b)}$
And similarly if $a$ goes into any other spot.
$\color{green}{(d, a, b, c)}$
$\color{green}{(c, a, d, b)}$
$\color{blue}{(b, a, d, c)}$
$\color{green}{(c, d, b, a)}$
$\color{green}{(b, c, d, a)}$
$\color{blue}{(d, c, b, a)}$