蹦床(trampoline)原理

4,758 阅读2分钟

摘录自 Functional JavaScript

来看一个相互递归的例子

function evenSteven(n) {
  if (n === 0)
    return true
  else
    return oddJohn(Math.abs(n) - 1);
}

function oddJohn(n) {
  if (n === 0)
    return false
  else
    return evenSteven(Math.abs(n) - 1);
}

两个函数相互回弹调用彼此,递减某个绝对值,直到一方到达零为止。这是一个相当优雅的解决方式。

evenSteven(4);
//=> true
oddJohn(11);
//=> true

尽管技术上可以实现尾递归的优化,但目前 JavaScript 引擎并不支持。因此在调用以上函数时可能会遇到这个错误:

evenSteven(100000);
// Uncaught RangeError: Maximum call stack size exceeded (or some variant)

这种错误称为“blowing the stack”,是因为 evenStevenoddJohn 互相调用过多造成了栈溢出。

可以是用蹦床(trampoline)原理的控制结构来消除这类错误。它的基本原理是,使用蹦床展平调用,而不是深度嵌套的递归调用。

首先看看如何来手动修复这两个函数使得递归不会溢出。一个方法是返回一个函数,它包装调用,而不是直接调用。可以使用 partial1 来实现这一点:

function partial1(fun, arg1) {
  return fun.bind(undefined, arg1);
}

这时对应的函数为:

``` js
function evenOline(n) {
  if (n === 0)
    return true;
  else
    return partial1(oddOline, Math.abs(n) - 1);
}

function oddOline(n) {
  if (n === 0)
    return false;
  else
    return partial1(evenOline, Math.abs(n) - 1);
}

这两个函数返回一个包装函数而不是直接进行 evenOlineoddOline 的互相调用。调用终止情况时都能正常工作:

evenOline(0);
//=> true
oddOline(0);
//=> true

现在可以手动调用递归来展平:

oddOline(3);
//=> function() { return evenOline(Math.abs(n) - 1) }
oddOline(3)();
//=> function() { return oddOline(Math.abs(n) - 1) }
oddOline(3)()();
//=> function() { return evenOline(Math.abs(n) - 1) }
oddOline(3)()()();
//=> true
oddOline(200000001)()()()(); //... a bunch more ()s

看起来能用了,但可以提供另外一个函数 trampoline,从程序执行来进行扁平化处理:

function trampoline(fun /*, args */) {
  var result = fun.apply(fun, _.rest(arguments));
  while (_.isFunction(result)) {
    result = result();
  }
  return result;
}

trampoline 所做的是不断调用函数的返回值,直到它不再是一个函数。具体是这样工作的:

trampoline(oddOline, 3);
//=> true
trampoline(evenOline, 200000);
//=> true
trampoline(oddOline, 300000);
//=> false
trampoline(evenOline, 200000000);
// wait a few seconds
//=> true

由于调用链的间接性,使用蹦床增加了相互递归函数的一些开销。然而,慢总比溢出好。如果不想强迫用户使用 trampoline,只是为了避免堆栈溢出,其实也可以隐藏其外观:

function isEvenSafe(n) {
  if (n === 0)
    return true;
  else
    return trampoline(partial1(oddOline, Math.abs(n) - 1));
}

function isOddSafe(n) {
  if (n === 0)
    return false;
  else
    return trampoline(partial1(evenOline, Math.abs(n) - 1));
}

试试能否正常工作:

isOddSafe(2000001);
//=> true
idEvenSafe(2000001);
//=> false