Here is a correct, linear-time implementation of subfactorial:<div><br></div><div><div><div>(defun subfactorial (n)</div><div>  "Subfactorial of the non-negative integer N."</div><div>  (check-type n (integer 0))</div>

<div>  (if (zerop n)</div><div>      1</div><div>    (do ((x 1 (1+ x))</div><div><span class="Apple-tab-span" style="white-space:pre">     </span> (a 0 (* x (+ a b)))</div><div><span class="Apple-tab-span" style="white-space:pre"> </span> (b 1 a))</div>

<div><span class="Apple-tab-span" style="white-space:pre">      </span>((= n x) a))))</div></div></div><div><br></div><div>and the corresponding test</div><div><br></div><div><div>(deftest subfactorial.1</div><div>    (mapcar #'subfactorial (iota 22))</div>

<div>  (1 0 1 2 9 44 265 1854 14833 133496 1334961 </div><div>   14684570 176214841 2290792932 32071101049 </div><div>   481066515734 7697064251745 130850092279664 </div><div>   2355301661033953 44750731559645106 </div><div>

   895014631192902121 18795307255050944540)).</div></div><div><br></div><div><br></div>