Javascript改变递归函数，带trampoline版本

Question

如何将以下代码更改为使用trampoline函数？谢谢。

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

首先，我将count编写为一个纯表达式

​

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))

​

然后，我将count转换为延续传递样式

​

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))

​

现在count已经处于尾部位置了，我们可以很容易地将它放在一个弹床上--当然，你可以使用任何你想要的弹床实现

​

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))

​

或者我们可以使用clojure风格的循环/递归弹床-我更喜欢这种风格，因为它确实需要一个辅助助手(即上面的countLoop )

​

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))

​