Linear Tail Recursion

by Julien Etienne

JavaScript

const isEvenTramp1 = (num) => {
  if (num === 0) return true
  if (num === 1) return false
  return () => isEvenTramp1(Math.abs(num) - 2) 
}

const tramp1  = (fn, ...params) => {
  let value = fn(...params)

  while (typeof value === 'function') value = value()
 
  return value
}

console.time('r1')
const r1 = tramp1(isEvenTramp1, 10_000_00)
console.timeEnd('r1')

/////////////////////////////////////////////////
// TCO
const tco = (f) => {
    var value
    var active = false
    var accumulated = []
  
    return function accumulator (...prams) {
      accumulated.push(prams)
  
      if (!active) {
        active = true
  
        while (accumulated.length) {
          value = f(...accumulated.shift())
        }
  
        active = false
  
        return value
      }
    }
  }

function tailRecursive(fn, ...args) {
  let result;
  function loop(acc) {
    result = fn(...acc);
    if (result !== undefined) {
      loop(result); // Tail call (assuming fn is tail-recursive)
    }
  }
  loop(args);
  return result;
}

function factorial(n, acc = 1) {
  if (n === 0) {
    return acc;
  }
  return tailRecursive(factorial, n - 1, n * acc);
}

console.time('r3')
//const r3 = tco(factorial(100000))
const r3 = factorial(1000)
console.log(r3)
console.timeEnd('r3')

//////////////////////////////////////////////////
// No recursion
const isEvenTramp2 = (num) => {
  if (num === 0) return true
  if (num === 1) return false
  return isEvenTramp2(Math.abs(num) - 2) 
}



console.time('r2')
const r2 = isEvenTramp2(10_000)
console.log(r2)
console.timeEnd('r2')