蹦床，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);
}

递归在基本情况与传入值相差很大时存在一个固有缺陷：大多数语言中，函数调用会利用程序的栈来存储数据。非常大的递归深度可能导致栈溢出。

如何避免这种情况呢？答案是使用“蹦床”技术。

蹦床策略的核心是让程序的一部分返回“值”或“延续”（后续处理的函数）。其流程大致如下：

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) 可以测试大型输入，而不会出现栈溢出错误。

以上就是蹦床，Java 中的示例的详细内容，更多请关注知识资源分享宝库其它相关文章！