Tail Call Optimization (TCO) and Trampoline optimization for recursive function

recursive_optimization.js

const startDate = new Date('2020-02-29 11:42:00')
const endDate = new Date('2020-03-02 17:49:23')

// Default Recursion
// const map = (fn, [head, ...tail]) => {
//   if (!head && tail.length === 0) {
//     return []
//   }
//   return [fn(head), ...map(fn, tail)]
// }

// TCO
// const map = (fn, [head, ...tail], acc = []) => {
//   if (!head && tail.length === 0) {
//     return acc
//   }
//   return map(fn, tail, [...acc, fn(head)])
// }

// Trampoline
const mapT = (fn, array) => {
  const func = function(fn, [head, ...tail], acc = []) {
    if (!head && tail.length === 0) {
      return acc
    }
    return func.bind(null, fn, tail, [...acc, fn(head)])
  }
  return trampoline(func(fn, array))
}

const trampoline = fn => {
  while (fn && fn instanceof Function) {
    fn = fn()
  }
  return fn
}

const double = x => x * 2
const bigArray = new Array(1000000).fill(Math.round(Math.random() * 9) + 1)
console.log(bigArray)

// console.time('rec')
// console.log(mapT(double, bigArray))
// console.timeEnd('rec')

console.time('it')
bigArray.map(double)
console.timeEnd('it')






// ================================================================================
// ================================================================================
//                                    FACTORIAL
// ================================================================================
// ================================================================================


const factorial = n => (n === 0 || n === 1 ? n : n * factorial(n - 1))
const factorialTco = (n, acc = 1) => (n === 0 || n === 1 ? acc : factorialTco(n - 1, n * acc))
const factorialTrampoline = n => {
  const func = (n, acc = 1) => {
    return n === 0 || n === 1 ? acc : func.bind(null, n - 1, n * acc)
  }
  return trampoline(func(n))
}
const factorialTrampolineTco = (n, acc = 1) => {
  const func = (n, acc = 1) => (n === 0 || n === 1 ? acc : func.bind(null, n - 1, n * acc))
  return trampoline(func(n, acc))
}

const trampoline = fn => {
  while (fn && fn instanceof Function) {
    fn = fn()
  }
  return fn
}

const factorialIt = n => {
  let a = 1
  for (let i = 1; i <= n; i++) {
    a = i * a
  }
  return a
}

console.time('factorial')
console.log(factorial(120))
console.timeEnd('factorial')

console.time('factorialTco')
console.log(factorialTco(120))
console.timeEnd('factorialTco')

console.time('factorialTrampoline')
console.log(factorialTrampoline(120))
console.timeEnd('factorialTrampoline')

console.time('factorialTrampolineTco')
console.log(factorialTrampolineTco(120))
console.timeEnd('factorialTrampolineTco')

console.time('factorialIt')
console.log(factorialIt(120))
console.timeEnd('factorialIt')