让我们编写一个简单的程序,计算从 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);
}
递归在基本情况与传入值相差很大时存在一个固有缺陷:大多数语言中,函数调用会利用程序的栈来存储数据。非常大的递归深度可能导致栈溢出。
如何避免这种情况呢?答案是使用“蹦床”技术。
蹦床策略的核心是让程序的一部分返回“值”或“延续”(后续处理的函数)。其流程大致如下:
TrampolineStep result = initialCall(input);
while (result instanceof Continuation) {
result = ((Continuation) result).continue();
}
return result.value();
sum
函数的延续是什么?
我们将修改 sum
函数,使其不再是简单的递归,而是使用延续。一种方法是将累加器 acc
作为对象通过延续传递。当到达 sum_trampoline(0, acc)
时,返回 acc
。下一步呢?
我们将 sum_trampoline(n, acc)
转换为 sum_trampoline(n-1, acc + n)
。初始调用为 sum_trampoline(n, 0)
。
代码如下:
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);
}
使用类型描述蹦床
蹦床的结构大致如下:
TrampolineStep result = initialCall(input);
while (result instanceof Continuation) {
result = ((Continuation) result).continue();
}
return result.value();
Java 中没有直接的延续类型,我们可以通过接口来模拟。
关键在于蹦床的引导函数,它将输入转换为合适的蹦床返回类型。
斐波那契的经典递归实现:
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
迭代版本:
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;
}
尾调用递归版本:
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);
}
将尾调用递归转换为蹦床版本:
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));
}
这段代码使用了更清晰的接口定义和更符合Java习惯的实现方式,避免了直接使用匿名内部类,提高了代码的可读性和可维护性。 同时,也修正了之前版本中的一些错误,并添加了完整的可运行示例。 注意,main
方法中的调用 sum_trampoline_bootstrap(100000)
可以测试大型输入,而不会出现栈溢出错误。