Y-Combinator, Fibonacci 10, 177 passes

Y-Combinator_test.js

const t = []

function yFib(n) {
  return (function(fn) {
    return fn(fn, n)
  })(function(fn, n) {
    t.push(n)
    if (n <= 1) {
      return n
    } else {
      return fn(fn, (n - 1)) + fn(fn, (n - 2))
    }
  })
}

// alternate approach with vars
function Y(f) {
  return (function(x) {
    return x(x)
  })(function(x) {
    return f(function(y) {
      return x(x)(y)
    })
  })
}

const YY = f => (x => x(x))(x => f(y => x(x)(y)))

// original variant
function fib(f) {
  return function (n) {
    t.push(n)
    return n <= 1 ? n : f(n - 1) + f(n - 2)
  }
}

// memoized variant
const fibMap = {}

function fib(f) {
  return function(n) {
    t.push(n)
    if (fibMap[String(n)]) {
      return fibMap[String(n)]
    } else {
      let z = n <= 1 ? n : f(n - 1) + f(n - 2)
      fibMap[String(n)] = z
      return z
    }
  }
}

const yyFib = Y(fib)

console.log(
  yyFib(10),
  t,
  t.length,
  t.reduce((a, c) => a + c, 0)
)
 
// The growth function for full recursion: `2*yyFib(n-1)-1`
  
// `node ./y.js` returns this for both `yFib(10)` and `yyFib(10)`:
// ---
// 55 [
//   10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1,
//    2, 1, 0, 3, 2, 1, 0, 1, 4, 3, 2, 1,
//    0, 1, 2, 1, 0, 5, 4, 3, 2, 1, 0, 1,
//    2, 1, 0, 3, 2, 1, 0, 1, 6, 5, 4, 3,
//    2, 1, 0, 1, 2, 1, 0, 3, 2, 1, 0, 1,
//    4, 3, 2, 1, 0, 1, 2, 1, 0, 7, 6, 5,
//    4, 3, 2, 1, 0, 1, 2, 1, 0, 3, 2, 1,
//    0, 1, 4, 3, 2, 1, 0, 1, 2, 1, 0, 5,
//    4, 3, 2, 1,
//   ... 77 more items
// ] 177 
//
// memoized
// ---
// 55 [
//   10, 9, 8, 7, 6, 5, 4,
//    3, 2, 1, 0, 1, 2, 3,
//    4, 5, 6, 7, 8
// ] 19