蹦床,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); }
递归问题?
递归在基本情况距离输入值很远时存在一个固有缺陷……在大多数语言中,函数调用使用程序的堆栈来存储函数调用信息,因此非常大的递归可能会导致堆栈溢出。
但是,有没有办法避免这种情况呢?实际上,有。这是一个古老的策略,称为“弹簧跳板”(trampoline)。
弹簧跳板
弹簧跳板策略的基本思想是,程序的一部分返回一个“值”或一个“延续”(continuation)。延续是什么?一个将继续处理的函数。
大致如下:
let trampolim = primeiraChamada(input); while (trampolim is continuation) { trampolim = trampolim.continue(); } return trampolim;
sum
的延续是什么?
让我们将sum
程序建模为:与其简单地递归,不如使用延续。一种方法是将acc
作为一种通过延续传递的对象。因此,当到达sum_trampoline(0, acc)
时,我们返回acc
。如何进行下一步呢?
让我们从sum_trampoline(n, acc)
到sum_trampoline(n-1, acc n)
。第一个输入是sum_trampoline(n, 0)
。
因此,代码如下:
Object sum_trampoline_bootstrap(int n) { return sum_trampoline(n, 0); } Object sum_trampoline(int n, int acc) { if (n == 0) { return acc; } return (Supplier<object>) () -> sum(n - 1, acc + n); }
使用类型描述弹簧跳板
弹簧跳板需要大致具有以下形式:
let trampolim = primeiraChamada(input); while (trampolim is continuation) { trampolim = trampolim.continue(); } return trampolim;
但这给了很大的编码自由度,对于Java世界来说并不十分直观。我们可以通过询问对象来检测是否为延续。如果我们询问“是否已找到值”呢?另一件事是,由于Java没有sum-types,return trampolim
实际上会返回trampolim
类型,而不是返回该值。我们可以返回trampolim.value()
。
最后,一个关键点是弹簧跳板的引导(bootstrapping)。为此,我们可以使用一个函数将输入转换为适当的弹簧跳板返回值。输入和结果可以被泛化以更好地使用:
public static <R> R trampoline(IN input, Function<IN, TrampolineStep<R>> trampolinebootStrap) { TrampolineStep<R> nextStep = trampolinebootStrap.apply(input); while (!nextStep.gotValue()) { nextStep = nextStep.runNextStep(); } return nextStep.value(); }
TrampolineStep<R>
接口呢?
它定义了三个方法:
gotValue
:询问是否已找到值value
:返回找到的值runNextStep
:返回一个值或一个延续
它基本上有两个状态:
- 已找到值
- 是一个延续
因此,我们可以使用静态方法来初始化它。对于已找到值的情况,需要传递值:
int sum(int n) { if (n == 0) { return 0; } return n + sum(n - 1); }
对于延续的情况,需要传递如何获取延续的下一个项目:
let trampolim = primeiraChamada(input); while (trampolim is continuation) { trampolim = trampolim.continue(); } return trampolim;
sum_trampoline
将如何实现?
Object sum_trampoline_bootstrap(int n) { return sum_trampoline(n, 0); } Object sum_trampoline(int n, int acc) { if (n == 0) { return acc; } return (Supplier<object>) () -> sum(n - 1, acc + n); }
尾调用斐波那契
斐波那契的经典实现遵循递归定义:
let trampolim = primeiraChamada(input); while (trampolim is continuation) { trampolim = trampolim.continue(); } return trampolim;
还有一个迭代版本,它非递归地展开斐波那契定义,而是向前推进:从0和1开始,直到达到相应的值:
public static <R> R trampoline(IN input, Function<IN, TrampolineStep<R>> trampolinebootStrap) { TrampolineStep<R> nextStep = trampolinebootStrap.apply(input); while (!nextStep.gotValue()) { nextStep = nextStep.runNextStep(); } return nextStep.value(); }
这个实现有一个向前推进的版本,使用“尾调用递归”:
static <X> TrampolineStep<X> valueFound(X value) { return new TrampolineStep() { @Override public boolean gotValue() { return true; } @Override public X value() { return value; } @Override public TrampolineStep<X> runNextStep() { return this; } }; }
这里我将输入接口分离出来,它准备了将在尾调用递归斐波那契中使用的数。由于它向前推进,我们从映射fib[0] => 0
, fib[1] => 1
开始,从索引0开始导航,直到到达索引n。
斐波那契:从尾调用到弹簧跳板
fib_tc
的例子很好地说明了斐波那契的弹簧跳板:
static <X> TrampolineStep<X> goonStep(Supplier<TrampolineStep<X>> x) { return new TrampolineStep() { @Override public boolean gotValue() { return false; } @Override public X value() { throw new RuntimeException("dont call this"); } @Override public TrampolineStep<X> runNextStep() { return x.get(); } }; }
请注意,这只是一个骨架,需要完整的TrampolineStep
接口实现以及trampoline
函数的完整实现才能编译和运行。 此外,IN
需要替换为具体的输入类型。
以上是蹦床,Java 中的示例的详细内容。更多信息请关注PHP中文网其他相关文章!

热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

Video Face Swap
使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热门文章

热工具

记事本++7.3.1
好用且免费的代码编辑器

SublimeText3汉化版
中文版,非常好用

禅工作室 13.0.1
功能强大的PHP集成开发环境

Dreamweaver CS6
视觉化网页开发工具

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)

公司安全软件导致部分应用无法正常运行的排查与解决方法许多公司为了保障内部网络安全,会部署安全软件。...

系统对接中的字段映射处理在进行系统对接时,常常会遇到一个棘手的问题:如何将A系统的接口字段有效地映�...

在使用MyBatis-Plus或其他ORM框架进行数据库操作时,经常需要根据实体类的属性名构造查询条件。如果每次都手动...

将姓名转换为数字以实现排序的解决方案在许多应用场景中,用户可能需要在群组中进行排序,尤其是在一个用...

在使用IntelliJIDEAUltimate版本启动Spring...

Java对象与数组的转换:深入探讨强制类型转换的风险与正确方法很多Java初学者会遇到将一个对象转换成数组的�...

电商平台SKU和SPU表设计详解本文将探讨电商平台中SKU和SPU的数据库设计问题,特别是如何处理用户自定义销售属...

在使用TKMyBatis进行数据库查询时,如何优雅地获取实体类变量名以构建查询条件,是一个常见的难题。本文将针...
