Javascript change recursive function with trampoline version

Question

How can the below code be changed to use the trampoline function? Thanks.

var count = function (n) {
    if(typeof n !== 'number' || n % 1 !== 0) return null;
    if(n < 3) { return 1; }
    console.log(n)
    return count(n - 1) + count(n - 3)
}

Answer 1

First, I start by writing count as a pure expression

const count = (n) =>
  n < 3
    ? 1
    : count (n - 1)
      + count (n - 3)

// demo
for (let n = 0; n < 10; n = n + 1)
  console.log (n, count (n))

Then I convert count to continuation-passing style

const count = (n, k = x => x) =>
  n < 3
    ? k (1)
    : count (n - 1, x =>
        count (n - 3, y =>
          k (x + y)))

// demo
for (let n = 0; n < 10; n = n + 1)
  console.log (n, count (n))

Now that count is in tail position, we can easily put this on a trampoline – you can use whichever trampoline implementation you want, of course

const countLoop = (n, k = x => x) =>
  n < 3
    ? k (1)
    : bounce (countLoop, n - 1, x =>
        bounce (countLoop, n - 3, y =>
          k (x + y)))

const count = (n) =>
  trampoline (countLoop (n))

const trampoline = (acc) =>
  {
    while (acc && acc.tag === bounce)
      acc = acc.f (...acc.values)
    return acc
  }

const bounce = (f, ...values) =>
  ({ tag: bounce, f, values })

// demo
for (let n = 0; n < 10; n = n + 1)
  console.log (n, count (n))

Or we can use a clojure-style loop/recur trampoline – I much prefer this style as it does require an auxiliary helper (ie countLoop above)

const count = (m) =>
  loop ((n = m, k = x => x) =>
    n < 3
      ? k (1)
      : recur (n - 1, x =>
          recur (n - 3, y =>
            k (x + y))))

const loop = (f) =>
  {
    let acc = f ()
    while (acc && acc.tag === recur)
      acc = f (...acc.values)
    return acc
  }

const recur = (...values) =>
  ({ tag: recur, values })

// demo
for (let n = 0; n < 10; n = n + 1)
  console.log (n, count (n))