让我们编写一个简单的程序，计算从 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)。
代码如下：
interface TrampolineStep { boolean gotValue(); T value(); TrampolineStep runNextStep();}class Continuation implements TrampolineStep { private final Supplier<TrampolineStep> nextStep; Continuation(Supplier<TrampolineStep> 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<TrampolineStep> 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) 可以测试大型输入，而不会出现栈溢出错误。
以上就是蹦床，Java 中的示例的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/191981.html
微信扫一扫 
支付宝扫一扫 
