如何重构二进制递归以使其与蹦床函数兼容？

Question

我编写了如下快速排序函数：

const quickSort = list => {
  if (list.length === 0) return list
  const [pivot, ...rest] = list
  const smaller = []
  const bigger = []
  for (x of rest) {
    x < pivot ? smaller.push(x) : bigger.push(x)
  }

  return [...quickSort(smaller), pivot, ...quickSort(bigger)]
}

我想把这个函数传递给蹦床函数，使它更有效。然而，为了使递归函数与trampoline兼容，我必须返回一个调用外部函数的函数。如下所示：

const trampoline = fn => (...args) => {
  let result = fn(...args)
  while (typeof result === "function") {
    result = result()
  }
  return result
}

const sumBelowRec = (number, sum = 0) => (
  number === 0
    ? sum
    : () => sumBelowRec(number - 1, sum + number)
)

const sumBelow = trampoline(sumBelowRec)
sumBelow(100000)
// returns 5000050000

如何转换快速排序功能，使其利用蹦床功能？

Answer 1

我看不出蹦床如何让你的快速排序更有效。如果您处于返回状态、具有值或处于进一步分割结果的状态、具有函数，则最不需要添加基于硬字符串的检查。这将大大增加计算时间。

你可以做的是使它更通用。总的来说，我认为蹦床是解释递归的好方法，但与直接函数调用相比，它在效率方面从来都不好。

此外，要利用trampoline，您必须创建一个返回函数或值的函数。但是您需要可以返回除法的s.th.（快速排序有两个递归子调用）。这就是您需要重用trampoline的方式（您的递归中的递归类型，您可能希望调用它的二级递归）。

const qs = (list) => {
  if (list.length === 0)
    return list;
  const [pivot, ...rest] = list;
  const smaller = [];
  const bigger = [];
  for (let x of rest) {
    x < pivot ? smaller.push(x) : bigger.push(x);
  }
  return [...trampoline(qs)(smaller), pivot, ...trampoline(qs)(bigger)];
};
const trampoline = fn => (...args) => {
  let result = fn(...args);
  while (typeof result === "function") {
    result = result();
  }
  return result;
};
console.log(trampoline(qs)([1, 6, 2, 4]));
console.log(trampoline(qs)([4, 5, 6, 1, 3, 2]));

Answer 2

要使用蹦床，您的递归函数必须是尾部递归的。您的快速排序函数不是尾部递归的，因为对快速排序的递归调用不会出现在尾部位置，即

return [...quickSort(smaller), pivot, ...quickSort(bigger)]

也许在程序中很难看到，但程序中的尾部调用是一个数组concat操作。如果不使用ES6语法编写，我们可以更容易地看到这一点

const a = quickSort(smaller)
const b = quickSort(bigger)
const res1 = a.concat(pivot)
const res2 = res1.concat(b) // <-- last operation is a concat
return res2

为了使快速排序（quickSort）具有递归性，我们可以使用延续传递样式来表示我们的程序。转换我们的程序很简单：我们通过向函数中添加一个参数来实现这一点，并使用它来指定计算应该如何继续。默认的延续是identity函数，它只将输入传递到输出–粗体更改

const identity = x => x

const quickSort = (list, cont = identity) => {
  if (list.length === 0)
    return cont(list)

  const [pivot, ...rest] = list
  const smaller = []
  const bigger = []
  for (const x of rest) { // don't forget const keyword for x here
    x < pivot ? smaller.push(x) : bigger.push(x)
  }

  return quickSort (smaller, a => quickSort (bigger, b => cont ([...a, pivot, ...b])))
}

现在我们可以看到，快速排序总是出现在尾部位置。然而，如果我们使用大量输入调用函数，直接递归将导致许多调用帧累积，最终溢出堆栈。为了防止这种情况发生，我们在蹦床上弹跳每个尾巴

const quickSort = (list, cont) => {
  if (list.length === 0)
    return bounce (cont, list);

  const [pivot, ...rest] = list
  const smaller = []
  const bigger = []
  for (const x of rest) {
    x < pivot ? smaller.push(x) : bigger.push(x)
  }

  return bounce (quickSort, smaller, a =>
           bounce (quickSort, larger, b =>
             bounce (cont, [...a, pivot, ...b])))
}

现在我们需要一个蹦床

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

const trampoline = t =>
{ while (t && t.tag === bounce)
    t = t.f (...t.args)
  return t
}

没错，这很有效

console.log (trampoline (quickSort ([ 6, 3, 4, 8, 1, 6, 2, 9, 5, 0, 7 ])))
// [ 0, 1, 2, 3, 4, 5, 6, 6, 7, 8, 9 ]

我们验证了它是否适用于大数据。100万个介于0到100万之间的数字。。。

const rand = () =>
  Math.random () * 1e6 >> 0

const big = 
  Array.from (Array (1e6), rand)

console.time ('1 million numbers')
console.log (trampoline (quickSort (big)))
console.timeEnd ('1 million numbers')
// [ 1, 1, 2, 4, 5, 5, 6, 6, 6, 7, ... 999990 more items ]
// 1 million numbers: 2213 ms

在我最近回答的另一个问题中，我展示了另外两个常见函数到延续传递样式的转换。

堆栈安全递归是我已经广泛介绍过的，关于这个主题有将近30个答案