目录
递归问题?
弹簧跳板
sum的延续是什么?
使用类型描述弹簧跳板
尾调用斐波那契
首页 Java java教程 蹦床,Java 中的示例

蹦床,Java 中的示例

Jan 17, 2025 pm 08:18 PM

Trampolim, exemplo em 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中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

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

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

公司安全软件导致应用无法运行?如何排查和解决? 公司安全软件导致应用无法运行?如何排查和解决? Apr 19, 2025 pm 04:51 PM

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

如何使用MapStruct简化系统对接中的字段映射问题? 如何使用MapStruct简化系统对接中的字段映射问题? Apr 19, 2025 pm 06:21 PM

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

如何优雅地获取实体类变量名构建数据库查询条件? 如何优雅地获取实体类变量名构建数据库查询条件? Apr 19, 2025 pm 11:42 PM

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

如何将姓名转换为数字以实现排序并保持群组中的一致性? 如何将姓名转换为数字以实现排序并保持群组中的一致性? Apr 19, 2025 pm 11:30 PM

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

IntelliJ IDEA是如何在不输出日志的情况下识别Spring Boot项目的端口号的? IntelliJ IDEA是如何在不输出日志的情况下识别Spring Boot项目的端口号的? Apr 19, 2025 pm 11:45 PM

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

Java对象如何安全地转换为数组? Java对象如何安全地转换为数组? Apr 19, 2025 pm 11:33 PM

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

电商平台SKU和SPU数据库设计:如何兼顾用户自定义属性和无属性商品? 电商平台SKU和SPU数据库设计:如何兼顾用户自定义属性和无属性商品? Apr 19, 2025 pm 11:27 PM

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

使用TKMyBatis进行数据库查询时,如何优雅地获取实体类变量名构建查询条件? 使用TKMyBatis进行数据库查询时,如何优雅地获取实体类变量名构建查询条件? Apr 19, 2025 pm 09:51 PM

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

See all articles