alt Hacker NewsI’ll re-read it, because clearly I don’t get it. And I’d like to.
My first two attempts made it seem like it was building on a function calling itself, with itself as an argument (so that it can call itself). I’m not sure how that isn’t recursion, and I didn’t read it as throwing away those approaches. But, as I say, I’ll re-read it…
author here. the idea is to see how the Y and Z combinators come out relatively naturally given an extremely constrained context with no loops, no recursion, no bindings. the article is intentionally structured as a sequence of failed attempts that progressively reveal which phenomenon is still responsible for the recursive behaviour.
in the article, i define recursion narrowly as "... call the function `fact` from inside the definition of the function `fact`".
you're right that `factgen` is also not recursive but it is also rejected, but for a different reason: self-reference. declarations are banned precisely because they give a function a "name" that can be referenced later.
please note that the solution which uses Z combinator (given at the end) grows from `(x => x(x))(x => x(x))`, which is NOT self-referential. it achieves self-replication by literally rewriting the content of the function twice, which is different from self-referential recursion of `factgen`.
hope that clears some of the confusion.