蹦床，Java 中的示例

让我们编写一个简单的程序，将从n到0的数字相加。但是，与其使用迭代方法，不如尝试递归方法？

我们将这个程序称为sum。我们知道sum(0) == 0，所以这是我们的基本情况。我们如何到达基本情况呢？sum(n) == n sum(n-1)，直到最终到达sum(0)。Java代码如下：

int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}

递归问题？

递归在基本情况距离输入值很远时存在一个固有缺陷……在大多数语言中，函数调用使用程序的堆栈来存储函数调用信息，因此非常大的递归可能会导致堆栈溢出。

但是，有没有办法避免这种情况呢？实际上，有。这是一个古老的策略，称为“弹簧跳板”（trampoline）。

弹簧跳板

弹簧跳板策略的基本思想是，程序的一部分返回一个“值”或一个“延续”（continuation）。延续是什么？一个将继续处理的函数。

大致如下：

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

sum的延续是什么？

让我们将sum程序建模为：与其简单地递归，不如使用延续。一种方法是将acc作为一种通过延续传递的对象。因此，当到达sum_trampoline(0, acc)时，我们返回acc。如何进行下一步呢？

让我们从sum_trampoline(n, acc)到sum_trampoline(n-1, acc n)。第一个输入是sum_trampoline(n, 0)。

因此，代码如下：

Object sum_trampoline_bootstrap(int n) {
    return sum_trampoline(n, 0);
}

Object sum_trampoline(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    return (Supplier<object>) () -> sum(n - 1, acc + n);
}

使用类型描述弹簧跳板

弹簧跳板需要大致具有以下形式：

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

但这给了很大的编码自由度，对于Java世界来说并不十分直观。我们可以通过询问对象来检测是否为延续。如果我们询问“是否已找到值”呢？另一件事是，由于Java没有sum-types，return trampolim实际上会返回trampolim类型，而不是返回该值。我们可以返回trampolim.value()。

最后，一个关键点是弹簧跳板的引导（bootstrapping）。为此，我们可以使用一个函数将输入转换为适当的弹簧跳板返回值。输入和结果可以被泛化以更好地使用：

public static <R> R trampoline(IN input,
                                   Function<IN, TrampolineStep<R>> trampolinebootStrap) {
  TrampolineStep<R> nextStep = trampolinebootStrap.apply(input);
  while (!nextStep.gotValue()) {
    nextStep = nextStep.runNextStep();
  }
  return nextStep.value();
}

TrampolineStep<r></r>接口呢？

它定义了三个方法：

• gotValue：询问是否已找到值
• value：返回找到的值
• runNextStep：返回一个值或一个延续

它基本上有两个状态：

• 已找到值
• 是一个延续

因此，我们可以使用静态方法来初始化它。对于已找到值的情况，需要传递值：

int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}

对于延续的情况，需要传递如何获取延续的下一个项目：

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

sum_trampoline将如何实现？

Object sum_trampoline_bootstrap(int n) {
    return sum_trampoline(n, 0);
}

Object sum_trampoline(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    return (Supplier<object>) () -> sum(n - 1, acc + n);
}

尾调用斐波那契

斐波那契的经典实现遵循递归定义：

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

还有一个迭代版本，它非递归地展开斐波那契定义，而是向前推进：从0和1开始，直到达到相应的值：

public static <R> R trampoline(IN input,
                                   Function<IN, TrampolineStep<R>> trampolinebootStrap) {
  TrampolineStep<R> nextStep = trampolinebootStrap.apply(input);
  while (!nextStep.gotValue()) {
    nextStep = nextStep.runNextStep();
  }
  return nextStep.value();
}

这个实现有一个向前推进的版本，使用“尾调用递归”：

static <X> TrampolineStep<X> valueFound(X value) {
    return new TrampolineStep() {
        @Override
        public boolean gotValue() {
            return true;
        }

        @Override
        public X value() {
            return value;
        }

        @Override
        public TrampolineStep<X> runNextStep() {
            return this;
        }
    };
}

这里我将输入接口分离出来，它准备了将在尾调用递归斐波那契中使用的数。由于它向前推进，我们从映射fib[0] => 0, fib[1] => 1开始，从索引0开始导航，直到到达索引n。

斐波那契：从尾调用到弹簧跳板

fib_tc的例子很好地说明了斐波那契的弹簧跳板：

static <X> TrampolineStep<X> goonStep(Supplier<TrampolineStep<X>> x) {
    return new TrampolineStep() {
        @Override
        public boolean gotValue() {
            return false;
        }

        @Override
        public X value() {
            throw new RuntimeException("dont call this");
        }

        @Override
        public TrampolineStep<X> runNextStep() {
            return x.get();
        }
    };
}

请注意，这只是一个骨架，需要完整的TrampolineStep接口实现以及trampoline函数的完整实现才能编译和运行。 此外，IN 需要替换为具体的输入类型。

以上是蹦床，Java 中的示例的详细内容。更多信息请关注PHP中文网其他相关文章！