蹦床功能工作原理

Question

​

function trampoline(f) {
  while (f && f instanceof Function) {
    f = f();
  }
  return f;
}
function sum(x, y) {
  if (y > 0) {
  //   return sum(x + 1, y - 1);  Maximum call stack size exceeded
  return sum.bind(null, x + 1, y - 1); //100001
  } else {
    return x;
  }
}
sum(1, 100000) //Maximum call stack size exceeded
let value= trampoline(sum(1, 100000))
console.log(value)

​

1. 为什么使用无堆栈溢出的蹦床功能？
2. 为什么蹦床函数中的和函数需要绑定？

Answer 1

1.为何使用无堆叠溢位的蹦床功能？

当function调用自身的次数超过限制时，将引发最大调用堆栈。在trampoline中有一个while循环，而不是recursion.so，它工作得很好。

2.为什么蹦床函数中的和函数需要绑定？

不需要使用bind()就可以做到这一点。使用绑定是因为它返回一个新的function。如果您仍然使用包装器函数，它可以正常工作。

​

function trampoline(f) {
  while (f && f instanceof Function) {
    f = f();
  }
  return f;
}
function sum(x, y) {
  if (y > 0) {
  //   return sum(x + 1, y - 1);  Maximum call stack size exceeded
  return () => sum(x + 1, y - 1); 
  } else {
    return x;
  }
}
sum(1, 100000) //Maximum call stack size exceeded
let value= trampoline(sum(1, 100000))
console.log(value)

​

您可能会问，为什么我们需要使用包装器函数。因为如果我们不使用包装函数，只需

return sum(x + 1, y - 1);

它会导致递归。当我们使用包装器函数或bind()时，会返回一个新的function，但不会调用它，因此会发生递归并引发错误。

Answer 2

让我们简化一下您的示例：

​

function sum_tramp(x, y) {
    if (y > 0)
        return () => sum_tramp(x + 1, y - 1);
    else
        return x;
}

function sum_rec(x, y) {
    if (y > 0)
        return sum_rec(x + 1, y - 1);
    else
        return x;
}

x = sum_tramp(1, 1e6)
while (x instanceof Function)
    x = x();
console.log(x)


x = sum_rec(1, 1e6) //Maximum call stack size exceeded
console.log(x)

​

朴素递归(sum_rec)要求在返回任何数据之前计算所有的值，因此要计算6+4，就必须计算需要8+2等的7+3。函数在所有后续调用完成之前都不会退出，并且在此之前它的参数位于堆栈上。

蹦床返回计算，即指示如何计算值而不是值本身。因为计算是已知的，所以函数会立即退出，不会填充堆栈。在主程序中，我们检查返回的值是否是一个计算，如果是，只需再次调用它。因此，在计算6+4时，我们会收到如何计算7+3的指令。我们执行这些指令，并得到如何计算8+2的指令。然后我们把它们拿出来..。以此类推，直到我们得到一个非函数的返回值。

正如注释中所指出的，一些浏览器已经实现了尾调用优化，这使得蹦床没有必要(但仍然值得了解)。