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

递归问题

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

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

立即学习“Java免费学习笔记（深入）”；

蹦床

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

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)。

代码如下：

918企业营销网站展示系统1.1

918企业营销网站展示系统是918团队专业开发，针对营销型企业，对页面美观需求偏高的企业开发！ 918企业营销网站展示系统前台： 1、首 页 2、关于我们 3、新闻中心 4、产品展示 5、案例展示 6、营销网络 7、品质保障 8、在线留言 9、联系方式 后台功能也很完善，美工也不错。栏目有 1、综合设置 2、公司介绍 3、产品管理 4、新闻管理 5、加盟招商 6、品质保障

下载

interface TrampolineStep {
    boolean gotValue();
    T value();
    TrampolineStep runNextStep();
}

class Continuation implements TrampolineStep {
    private final Supplier> nextStep;

    Continuation(Supplier> nextStep) {
        this.nextStep = nextStep;
    }

    @Override
    public boolean gotValue() {
        return false;
    }

    @Override
    public T value() {
        throw new RuntimeException("Don't call this");
    }

    @Override
    public TrampolineStep runNextStep() {
        return nextStep.get();
    }
}

class Value implements TrampolineStep {
    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 runNextStep() {
        return this;
    }
}


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

TrampolineStep 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 trampoline(Supplier> trampolineBootstrap) {
    TrampolineStep 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 fib_bootstrap(int n) {
    return fib_trampoline(0, 1, 0, n);
}

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