Y Combinator

y.js

// Y Combinator

// λf.(λg.f(λy.g g y))(λg.f(λy.g g y))
//
// derives the fixed-point of the input function 
// such that Y( f ) and f( Y( f ) ) are computationally equivalent

function Y( f ) {
  return (function( g ) {
    return f(function( y ) {
      return g( g )( y );
    });
  })(function( g ) {
    return f(function( y ) {
      return g( g )( y );
    });
  });
}

// factorial generator

function factGen( factorial ) {
  return function( n ) {
    return n == 0 ? 1 : n * factorial( n - 1 );
  };
}

// create a factorial function

var fact = Y( factGen );

fact( 5 );

// so, combining all of this, you can write a single, pure functional
// expression with no variable declarations, no assignments, and no loops
// that's still able to do recursion

(function( f ) {
  return (function( g ) {
    return f(function( y ) {
      return g( g )( y );
    });
  })(function( g ) {
    return f(function( y ) {
      return g( g )( y );
    });
  });
})(function( factorial ) {
  return function( n ) {
    return n === 0 ? 1 : n * factorial( n - 1 );
  }
})( 5 );

// In ES 6, this can be written in a style that better reflects the functional
// nature of what's going on.
//
// The lambda calculus notation λf.(λg.f(λy.g g y))(λg.f(λy.g g y))
// can be written as f => ( g => f( y => g( g )( y ) ) )( g => f( y => g( g )( y ) ) )
//
// with some better formatting, and adding in the anonymous factorial generator
// at the end, it looks like this...

( f => 
  ( g => 
    f( y => 
      g( g )( y ) 
    ) 
  )( g => 
    f( y => 
      g( g )( y ) 
    ) 
  ) 
)(factorial => 
  n => n === 0 ? 1 : n * factorial( n - 1 )
)( 5 );