When did the first recursive Factorial program appear? As a non-descript piece of code flagged as Algorithm 33 in Communications of the ACM, Volume 4 Issue 2, Feb. 1961. The code is written in Algol 60, as Algol was the first procedural language to allow recursion (i.e. Lisp allowed recursion, but was not a procedural language).
Strangely enough, the algorithm is so overlooked, searching for “Algorithm 33” in the ACM digital library does not find it… you have to search manually through the issues online.