6 ms·
The Y combinator lets you implement recursion without using recursion. For example, a Javascript closure can't refer to itself. But if we define the (strict) Y
by justinpombrio 4y ago
The Y combinator lets you implement recursion without using recursion. For example, a Javascript closure can't refer to itself. But if we define the (strict) Y combinator using JS closures:
let Y = f => (x => x(x))(x => f(z => x(x)(z)))
then we can call it, again only using closures, and define a function that sums the numbers from 1 to N by "calling itself":
let sumToN = Y(sumToN => n => n == 0 ? 0 : n + sumToN(n-1))
sumToN(4)
// -> 10
In practice, no one actually implements recursion this way because it would be slow. So instead it's more of a statement about the expressiveness of languages, and how "we have recursion!" doesn't actually give you any power you didn't have before, if you had functions.