让我们编写一个简单的程序，计算从 n 到 0 的数字之和。通常我们会使用迭代，但这次我们尝试递归方法。
我们将此程序命名为 sum。已知 sum(0) == 0，这是我们的基本情况。sum(n) 可以表示为 n + sum(n-1)，直到最终计算 sum(0)。Java 代码如下：
<code class="java">int sum(int n) {
if (n == 0) {
return 0;
}
return n + sum(n - 1);
}</code>
递归问题
递归在基本情况与传入值相差很大时存在一个固有缺陷：大多数语言中，函数调用会利用程序的栈来存储数据。非常大的递归深度可能导致栈溢出。
如何避免这种情况呢？答案是使用“蹦床”技术。
立即学习“Java免费学习笔记（深入）”；
蹦床
蹦床策略的核心是让程序的一部分返回“值”或“延续”（后续处理的函数）。其流程大致如下：
<code class="java">TrampolineStep result = initialCall(input);
while (result instanceof Continuation) {
result = ((Continuation) result).continue();
}
return result.value();</code>
sum 函数的延续是什么？
我们将修改 sum 函数，使其不再是简单的递归，而是使用延续。一种方法是将累加器 acc 作为对象通过延续传递。当到达 sum_trampoline(0, acc) 时，返回 acc。下一步呢？
我们将 sum_trampoline(n, acc) 转换为 sum_trampoline(n-1, acc + n)。初始调用为 sum_trampoline(n, 0)。
代码如下：
<code class="java">interface TrampolineStep<T> {
boolean gotValue();
T value();
TrampolineStep<T> runNextStep();
}
class Continuation<T> implements TrampolineStep<T> {
private final Supplier<TrampolineStep<T>> nextStep;
Continuation(Supplier<TrampolineStep<T>> nextStep) {
this.nextStep = nextStep;
}
@Override
public boolean gotValue() {
return false;
}
@Override
public T value() {
throw new RuntimeException("Don't call this");
}
@Override
public TrampolineStep<T> runNextStep() {
return nextStep.get();
}
}
class Value<T> implements TrampolineStep<T> {
private final T value;
Value(T value) {
this.value = value;
}
@Override
public boolean gotValue() {
return true;
}
@Override
public T value() {
return value;
}
@Override
public TrampolineStep<T> runNextStep() {
return this;
}
}
TrampolineStep<Integer> sum_trampoline_bootstrap(int n) {
return sum_trampoline(n, 0);
}
TrampolineStep<Integer> sum_trampoline(int n, int acc) {
if (n == 0) {
return new Value<>(acc);
}
return new Continuation<>(() -> sum_trampoline(n - 1, acc + n));
}
public static <R> R trampoline(Supplier<TrampolineStep<R>> trampolineBootstrap) {
TrampolineStep<R> nextStep = trampolineBootstrap.get();
while (!nextStep.gotValue()) {
nextStep = nextStep.runNextStep();
}
return nextStep.value();
}
public static void main(String[] args) {
int result = trampoline(() -> sum_trampoline_bootstrap(100000));
System.out.println(result);
}</code>
使用类型描述蹦床
蹦床的结构大致如下：
<code class="java">TrampolineStep result = initialCall(input);
while (result instanceof Continuation) {
result = ((Continuation) result).continue();
}
return result.value();</code>
Java 中没有直接的延续类型，我们可以通过接口来模拟。
关键在于蹦床的引导函数，它将输入转换为合适的蹦床返回类型。
尾调用斐波那契
斐波那契的经典递归实现：
<code class="java">int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}</code>
迭代版本：
<code class="java">int fib_iterativo(int n) {
int a = 0, b = 1;
if (n == 0) return a;
for (int i = 1; i < n; i++) {
int temp = a + b;
a = b;
b = temp;
}
return b;
}</code>
尾调用递归版本：
<code class="java">int fib_tc_entrada(int n) {
return fib_tc(0, 1, 0, n);
}
int fib_tc(int a, int b, int i, int n) {
if (i == n) return a;
return fib_tc(b, a + b, i + 1, n);
}</code>
将尾调用递归转换为蹦床版本：
<code class="java">TrampolineStep<Integer> fib_bootstrap(int n) {
return fib_trampoline(0, 1, 0, n);
}
TrampolineStep<Integer> fib_trampoline(int a, int b, int i, int n) {
if (i == n) {
return new Value<>(a);
}
return new Continuation<>(() -> fib_trampoline(b, a + b, i + 1, n));
}</code>
这段代码使用了更清晰的接口定义和更符合Java习惯的实现方式，避免了直接使用匿名内部类，提高了代码的可读性和可维护性。 同时，也修正了之前版本中的一些错误，并添加了完整的可运行示例。 注意，main 方法中的调用 sum_trampoline_bootstrap(100000) 可以测试大型输入，而不会出现栈溢出错误。
