蹦床为什么起作用？

/*not the fanciest, it's just meant to
reenforce that I know what I'm doing.*/

function loopy(x){
    if (x<10000000){ 
        return function(){
            return loopy(x+1)
        }
    }else{
        return x;
    }
};

function trampoline(foo){
    while(foo && typeof foo === 'function'){
        foo = foo();
    }
    return foo;
/*I've seen trampolines without this,
mine wouldn't return anything unless
I had it though. Just goes to show I
only half know what I'm doing.*/
};

alert(trampoline(loopy(0)));

#1 楼

您的大脑反抗loopy()函数的原因是它的类型不一致：

function loopy(x){
    if (x<10000000){ 
        return function(){ // On this line it returns a function...
            // (This is not part of loopy(), this is the function we are returning.)
            return loopy(x+1)
        }
    }else{
        return x; // ...but on this line it returns an integer!
    }
};

很多语言甚至都不允许您做类似的事情这个，或者至少需要更多的打字来解释这应该有什么意义。因为确实没有。函数和整数是完全不同的对象。

因此，让我们仔细检查一下while循环：

while(foo && typeof foo === 'function'){
    foo = foo();
}

最初，foo等于至loopy(0)。什么是loopy(0)？好吧，它小于10000000，所以我们得到function(){return loopy(1)}。这是一个真实的值，它是一个函数，因此循环继续进行。

现在我们来看看foo = foo()。 foo()与loopy(1)相同。由于1仍小于10000000，将返回function(){return loopy(2)}，然后将其分配给foo。

foo仍然是一个函数，因此我们继续进行操作，直到最终foo等于function(){return loopy(10000000)}为止。那是一个函数，所以我们再做一次foo = foo()，但是这一次，当我们调用loopy(10000000)时，x不小于10000000，所以我们只得到x即可。由于10000000也不是一个函数，因此也会结束while循环。

#2 楼

凯文（Kevin）简洁地指出了此特定代码段是如何工作的（以及为什么它很难理解），但我想补充一些有关蹦床在一般工作中的工作方式的信息。每个函数调用都会向当前执行堆栈中添加一个堆栈框架。假设我们有一个打印数字倒数的函数：

function countdown(n) {
  if (n === 0) {
    console.log("Blastoff!");
  } else {
    console.log("Launch in " + n);
    countdown(n - 1);
  }
}

如果调用countdown(3)，让我们分析没有TCO时调用堆栈的外观。

> countdown(3);
// stack: countdown(3)
Launch in 3
// stack: countdown(3), countdown(2)
Launch in 2
// stack: countdown(3), countdown(2), countdown(1)
Launch in 1
// stack: countdown(3), countdown(2), countdown(1), countdown(0)
Blastoff!
// returns, stack: countdown(3), countdown(2), countdown(1)
// returns, stack: countdown(3), countdown(2)
// returns, stack: countdown(3)
// returns, stack is empty

使用TCO，对countdown的每个递归调用都位于尾部位置（除了返回调用结果之外，别无他法），因此不分配堆栈帧。如果没有TCO，则即使n稍大，堆栈也会炸毁。

通过在countdown函数周围插入包装器，油菜籽油可以解决此限制。然后，countdown不执行递归调用，而是立即返回要调用的函数。下面是一个示例实现：

function trampoline(firstHop) {
  nextHop = firstHop();
  while (nextHop) {
    nextHop = nextHop()
  }
}

function countdown(n) {
  trampoline(() => countdownHop(n));
}

function countdownHop(n) {
  if (n === 0) {
    console.log("Blastoff!");
  } else {
    console.log("Launch in " + n);
    return () => countdownHop(n-1);
  }
}

为了更好地了解其工作原理，让我们看一下调用堆栈：

> countdown(3);
// stack: countdown(3)
// stack: countdown(3), trampoline
// stack: countdown(3), trampoline, countdownHop(3)
Launch in 3
// return next hop from countdownHop(3)
// stack: countdown(3), trampoline
// trampoline sees hop returned another hop function, calls it
// stack: countdown(3), trampoline, countdownHop(2)
Launch in 2
// stack: countdown(3), trampoline
// stack: countdown(3), trampoline, countdownHop(1)
Launch in 1
// stack: countdown(3), trampoline
// stack: countdown(3), trampoline, countdownHop(0)
Blastoff!
// stack: countdown(3), trampoline
// stack: countdown(3)
// stack is empty

在每个步骤中，countdownHop函数都会放弃对接下来发生的事情的直接控制，而是返回一个调用来描述接下来要发生的事情。然后，蹦床函数会接受并调用它，然后再调用返回的任何函数，依此类推，直到没有“下一步”为止。之所以称其为蹦床，是因为每个递归调用与蹦床实现之间的控制流“反弹”，而不是直接重复执行该函数。通过放弃对谁进行递归调用的控制，蹦床功能可以确保堆栈不会太大。旁注：trampoline的此实现为简单起见省略了返回值。

要知道这是否是一个好主意可能很棘手。由于分配新封包的每个步骤都会降低性能。明智的优化可以使之可行，但您永远不会知道。 Trampolining在解决硬递归限制方面非常有用，例如，当语言实现设置最大调用堆栈大小时。

#3 楼

如果使用专用返回类型（而不是滥用函数）实现蹦床，可能会变得更容易理解：



是什么原因阻止了trampoline导致堆栈溢出？


它不再自称。相反，它返回一个结果（在我的实现中为foo = foo()），该结果传达是继续进行递归还是中断该循环。我想念什么吗？也许这只是必要的邪恶。


是的，这正是循环的必要邪恶。一个人也可以写没有突变的Result，但是它又需要递归：

class Result {}
// poor man's case classes
class Recurse extends Result {
    constructor(a) { this.arg = a; }
}
class Return extends Result {
    constructor(v) { this.value = v; }
}

function loopy(x) {
    if (x<10000000)
        return new Recurse(x+1);
    else
        return new Return(x);
}

function trampoline(fn, x) {
    while (true) {
        const res = fn(x);
        if (res instanceof Recurse)
            x = res.arg;
        else if (res instanceof Return)
            return res.value;
    }
}

alert(trampoline(loopy, 0));

它仍然显示出蹦床功能甚至更好的想法。 />
践踏的要点是从想要使用递归的函数中提取尾递归调用，并将其抽象为返回值，然后仅在一个地方进行实际的递归-foo = foo()函数，然后可以对其进行优化在一个地方使用循环。