错排的递推思路
第一种缩减问题规模，将第 n 位数与前 n - 1 个数进行交换，共有 n - 1 种交换方法，这里是和原来没有错排的位置交换。此时，问题规模由 n 位数错排缩减为 n - 2 位数的错排了 Dₙ₋₂，即 (n - 1)Dₙ₋₂ 种错排。
第二种方法扩展已知错排序列长度。已知 n - 1 位错排 Dₙ₋₁，当新增第ｎ位时，将新增的与前 n - 1 位中任意一个交换，这里是和错排过的位置交换，即可得到 n 位错排，共 (n - 1)Dₙ₋₁ 种错排。
第一种方法将原正确位置的数交换到了第 n 位；第二种方法由于是已经错排过了，所以交换的位置一定不是原位置正确的那个数，所以两种方法不会产生重复。
由正确位置交换和不正确位置交换加起来就是所有与第 n 位交换产生的错排：Dₙ = (n-1)(Dₙ₋₂ + Dₙ₋₁)，初始 D₁ = 0，D₂ = 1，计算可得 D₀ = 1。
