How does Y-combinator compute the fixed point programmatically?
<p>I believe I understand mathematically the idea of Y-combinator: it returns the fixed point of a given functional <code>F</code>, thus <code>f = Y(F)</code> where <code>f</code> satisfies <code>f == F(f)</code>. </p>

<p>But I don't understand how it does the actual computation program wise?</p>

<p>Let's take the javascript example given <a href="http://matt.might.net/articles/implementation-of-recursive-fixed-point-y-combinator-in-javascript-for-memoization/" rel="nofollow noreferrer">here</a>:</p>

<pre><code>var Y = (F) =&gt; ( x =&gt; F( y =&gt; x(x)(y) ) )( x =&gt; F( y =&gt; x(x)(y) ) )
var Factorial = (factorial) =&gt; (n =&gt; n == 0 ? 1 : n * factorial(n-1))

Y(Factorial)(6) == 720    // =&gt; true
computed_factorial = Y(Factorial)
</code></pre>

<p>The part I don’t understand is how the <code>computed_factorial</code> function (the fixed point) actually get computed? By tracing the definition of Y, you’ll find it runs into a <strong>infinitely recursion</strong> at the <code>x(x)</code> part, I can't see any terminating case implied there. However, it strangely does return. Can anyone explain?</p>