Lambda 表达式对递归的优化 (上) - 使用尾递归

本贴最后更新于 1516 天前,其中的信息可能已经时异事殊

原文链接

递归优化
很多算法都依赖于递归,典型的比如分治法(Divide-and-Conquer)。但是普通的递归算法在处理规模较大的问题时,常常会出现 StackOverflowError。处理这个问题,我们可以使用一种叫做尾调用(Tail-Call Optimization)的技术来对递归进行优化。同时,还可以通过暂存子问题的结果来避免对子问题的重复求解,这个优化方法叫做备忘录(Memoization)。

本文首先对尾递归进行介绍,下一票文章中会对备忘录模式进行介绍。

使用尾调用优化
当递归算法应用于大规模的问题时,容易出现 StackOverflowError,这是因为需要求解的子问题过多,递归嵌套层次过深。这时,可以采用尾调用优化来避免这一问题。该技术之所以被称为尾调用,是因为在一个递归方法中,最后一个语句才是递归调用。这一点和常规的递归方法不同,常规的递归通常发生在方法的中部,在递归结束返回了结果后,往往还会对该结果进行某种处理。

Java 在编译器级别并不支持尾递归技术。但是我们可以借助 Lambda 表达式来实现它。下面我们会通过在阶乘算法中应用这一技术来实现递归的优化。以下代码是没有优化过的阶乘递归算法:

public class Factorial {
public static int factorialRec(final int number) {
if(number == 1)
return number;
else
return number * factorialRec(number - 1);
}
}
以上的递归算法在处理小规模的输入时,还能够正常求解,但是输入大规模的输入后就很有可能抛出 StackOverflowError:

try {
System.out.println(factorialRec(20000));
} catch(StackOverflowError ex) {
System.out.println(ex);
}

// java.lang.StackOverflowError
出现这个问题的原因不在于递归本身,而在于在等待递归调用结束的同时,还需要保存了一个 number 变量。因为递归方法的最后一个操作是乘法操作,当求解一个子问题时(factorialRec(number - 1)),需要保存当前的 number 值。所以随着问题规模的增加,子问题的数量也随之增多,每个子问题对应着调用栈的一层,当调用栈的规模大于 JVM 设置的阈值时,就发生了 StackOverflowError。

转换成尾递归
转换成尾递归的关键,就是要保证对自身的递归调用是最后一个操作。不能像上面的递归方法那样:最后一个操作是乘法操作。而为了避免这一点,我们可以先进行乘法操作,将结果作为一个参数传入到递归方法中。但是仅仅这样仍然是不够的,因为每次发生递归调用时还是会在调用栈中创建一个栈帧(Stack Frame)。随着递归调用深度的增加,栈帧的数量也随之增加,最终导致 StackOverflowError。可以通过将递归调用延迟化来避免栈帧的创建,以下代码是一个原型实现:

public static TailCall factorialTailRec(
final int factorial, final int number) {
if (number == 1)
return TailCalls.done(factorial);
else
return TailCalls.call(() -> factorialTailRec(factorial * number, number - 1));
}
需要接受的参数 factorial 是初始值,而 number 是需要计算阶乘的值。 我们可以发现,递归调用体现在了 call 方法接受的 Lambda 表达式中。以上代码中的 TailCall 接口和 TailCalls 工具类目前还没有实现。

创建 TailCall 函数接口
TailCall 的目标是为了替代传统递归中的栈帧,通过 Lambda 表达式来表示多个连续的递归调用。所以我们需要通过当前的递归操作得到下一个递归操作,这一点有些类似 UnaryOperator 函数接口的 apply 方法。同时,我们还需要方法来完成这几个任务:

判断递归是否结束了
得到最后的结果
触发递归
因此,我们可以这样设计 TailCall 函数接口:

@FunctionalInterface
public interface TailCall {
TailCall apply();
default boolean isComplete() { return false; }
default T result() { throw new Error("not implemented"); }
default T invoke() {
return Stream.iterate(this, TailCall::apply)
.filter(TailCall::isComplete)
.findFirst()
.get()
.result();
}
}
isComplete,result 和 invoke 方法分别完成了上述提到的 3 个任务。只不过具体的 isComplete 和 result 还需要根据递归操作的性质进行覆盖,比如对于递归的中间步骤,isComplete 方法可以返回 false,然而对于递归的最后一个步骤则需要返回 true。对于 result 方法,递归的中间步骤可以抛出异常,而递归的最终步骤则需要给出结果。

invoke 方法则是最重要的一个方法,它会将所有的递归操作通过 apply 方法串联起来,通过没有栈帧的尾调用得到最后的结果。串联的方式利用了 Stream 类型提供的 iterate 方法,它本质上是一个无穷列表,这也从某种程度上符合了递归调用的特点,因为递归调用发生的数量虽然是有限的,但是这个数量也可以是未知的。而给这个无穷列表画上终止符的操作就是 filter 和 findFirst 方法。因为在所有的递归调用中,只有最后一个递归调用会在 isComplete 中返回 true,当它被调用时,也就意味着整个递归调用链的结束。最后,通过 findFirst 来返回这个值。

如果不熟悉 Stream 的 iterate 方法,可以参考上一篇文章,在其中对该方法的使用进行了介绍。

创建 TailCalls 工具类
在原型设计中,会调用 TailCalls 工具类的 call 和 done 方法:

call 方法用来得到当前递归的下一个递归
done 方法用来结束一系列的递归操作,得到最终的结果
public class TailCalls {
public static TailCall call(final TailCall nextCall) {
return nextCall;
}
public static TailCall done(final T value) {
return new TailCall() {
@Override public boolean isComplete() { return true; }
@Override public T result() { return value; }
@Override public TailCall apply() {
throw new Error("end of recursion");
}
};
}
}
在 done 方法中,我们返回了一个特殊的 TailCall 实例,用来代表最终的结果。注意到它的 apply 方法被实现成被调用抛出异常,因为对于最终的递归结果,是没有后续的递归操作的。

以上的 TailCall 和 TailCalls 虽然是为了解决阶乘这一简单的递归算法而设计的,但是它们无疑在任何需要尾递归的算法中都能够派上用场。

使用尾递归函数
使用它们来解决阶乘问题的代码很简单:

System.out.println(factorialTailRec(1, 5).invoke()); // 120
System.out.println(factorialTailRec(1, 20000).invoke()); // 0
第一个参数代表的是初始值,第二个参数代表的是需要计算阶乘的值。

但是在计算 20000 的阶乘时得到了错误的结果,这是因为整型数据无法容纳这么大的结果,发生了溢出。对于这种情况,可以使用 BigInteger 来代替 Integer 类型。

实际上 factorialTailRec 的第一个参数是没有必要的,在一般情况下初始值都应该是 1。所以我们可以做出相应地简化:

public static int factorial(final int number) {
return factorialTailRec(1, number).invoke();
}

// 调用方式
System.out.println(factorial(5));
System.out.println(factorial(20000));
使用 BigInteger 代替 Integer
主要就是需要定义 decrement 和 multiple 方法来帮助完成大整型数据的阶乘操作:

public class BigFactorial {
public static BigInteger decrement(final BigInteger number) {
return number.subtract(BigInteger.ONE);
}

public static BigInteger multiply( final BigInteger first, final BigInteger second) { return first.multiply(second); } final static BigInteger ONE = BigInteger.ONE; final static BigInteger FIVE = new BigInteger("5"); final static BigInteger TWENTYK = new BigInteger("20000"); //... private static TailCall<BigInteger> factorialTailRec( final BigInteger factorial, final BigInteger number) { if(number.equals(BigInteger.ONE)) return done(factorial); else return call(() -> factorialTailRec(multiply(factorial, number), decrement(number))); } public static BigInteger factorial(final BigInteger number) { return factorialTailRec(BigInteger.ONE, number).invoke(); }

}

  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3201 引用 • 8216 回帖 • 3 关注
  • Lambda
    24 引用 • 19 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
zhaozhizheng
没有人会关心你付出过多少努力,撑得累不累,摔得痛不痛,他们只会看你最后站在什么位置,然后羡慕或者鄙夷

推荐标签 标签

  • Hadoop

    Hadoop 是由 Apache 基金会所开发的一个分布式系统基础架构。用户可以在不了解分布式底层细节的情况下,开发分布式程序。充分利用集群的威力进行高速运算和存储。

    93 引用 • 122 回帖 • 619 关注
  • wolai

    我来 wolai:不仅仅是未来的云端笔记!

    2 引用 • 14 回帖 • 5 关注
  • 大数据

    大数据(big data)是指无法在一定时间范围内用常规软件工具进行捕捉、管理和处理的数据集合,是需要新处理模式才能具有更强的决策力、洞察发现力和流程优化能力的海量、高增长率和多样化的信息资产。

    89 引用 • 113 回帖
  • Thymeleaf

    Thymeleaf 是一款用于渲染 XML/XHTML/HTML5 内容的模板引擎。类似 Velocity、 FreeMarker 等,它也可以轻易的与 Spring 等 Web 框架进行集成作为 Web 应用的模板引擎。与其它模板引擎相比,Thymeleaf 最大的特点是能够直接在浏览器中打开并正确显示模板页面,而不需要启动整个 Web 应用。

    11 引用 • 19 回帖 • 395 关注
  • golang

    Go 语言是 Google 推出的一种全新的编程语言,可以在不损失应用程序性能的情况下降低代码的复杂性。谷歌首席软件工程师罗布派克(Rob Pike)说:我们之所以开发 Go,是因为过去 10 多年间软件开发的难度令人沮丧。Go 是谷歌 2009 发布的第二款编程语言。

    500 引用 • 1395 回帖 • 243 关注
  • Visio
    1 引用 • 2 回帖 • 1 关注
  • etcd

    etcd 是一个分布式、高可用的 key-value 数据存储,专门用于在分布式系统中保存关键数据。

    6 引用 • 26 回帖 • 541 关注
  • Lute

    Lute 是一款结构化的 Markdown 引擎,支持 Go 和 JavaScript。

    29 引用 • 202 回帖 • 28 关注
  • Eclipse

    Eclipse 是一个开放源代码的、基于 Java 的可扩展开发平台。就其本身而言,它只是一个框架和一组服务,用于通过插件组件构建开发环境。

    76 引用 • 258 回帖 • 628 关注
  • ngrok

    ngrok 是一个反向代理,通过在公共的端点和本地运行的 Web 服务器之间建立一个安全的通道。

    7 引用 • 63 回帖 • 654 关注
  • 机器学习

    机器学习(Machine Learning)是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能。

    77 引用 • 37 回帖 • 1 关注
  • Sym

    Sym 是一款用 Java 实现的现代化社区(论坛/BBS/社交网络/博客)系统平台。

    下一代的社区系统,为未来而构建

    524 引用 • 4601 回帖 • 710 关注
  • OpenStack

    OpenStack 是一个云操作系统,通过数据中心可控制大型的计算、存储、网络等资源池。所有的管理通过前端界面管理员就可以完成,同样也可以通过 Web 接口让最终用户部署资源。

    10 引用 • 1 关注
  • DevOps

    DevOps(Development 和 Operations 的组合词)是一组过程、方法与系统的统称,用于促进开发(应用程序/软件工程)、技术运营和质量保障(QA)部门之间的沟通、协作与整合。

    59 引用 • 25 回帖
  • 导航

    各种网址链接、内容导航。

    45 引用 • 177 回帖
  • 开源

    Open Source, Open Mind, Open Sight, Open Future!

    412 引用 • 3588 回帖 • 1 关注
  • Docker

    Docker 是一个开源的应用容器引擎,让开发者可以打包他们的应用以及依赖包到一个可移植的容器中,然后发布到任何流行的操作系统上。容器完全使用沙箱机制,几乎没有性能开销,可以很容易地在机器和数据中心中运行。

    497 引用 • 934 回帖
  • 博客

    记录并分享人生的经历。

    273 引用 • 2388 回帖
  • RIP

    愿逝者安息!

    8 引用 • 92 回帖 • 404 关注
  • Pipe

    Pipe 是一款小而美的开源博客平台。Pipe 有着非常活跃的社区,可将文章作为帖子推送到社区,来自社区的回帖将作为博客评论进行联动(具体细节请浏览 B3log 构思 - 分布式社区网络)。

    这是一种全新的网络社区体验,让热爱记录和分享的你不再感到孤单!

    134 引用 • 1127 回帖 • 110 关注
  • CodeMirror
    2 引用 • 17 回帖 • 166 关注
  • 服务

    提供一个服务绝不仅仅是简单的把硬件和软件累加在一起,它包括了服务的可靠性、服务的标准化、以及对服务的监控、维护、技术支持等。

    41 引用 • 24 回帖
  • API

    应用程序编程接口(Application Programming Interface)是一些预先定义的函数,目的是提供应用程序与开发人员基于某软件或硬件得以访问一组例程的能力,而又无需访问源码,或理解内部工作机制的细节。

    79 引用 • 431 回帖
  • 工具

    子曰:“工欲善其事,必先利其器。”

    299 引用 • 764 回帖
  • 小薇

    小薇是一个用 Java 写的 QQ 聊天机器人 Web 服务,可以用于社群互动。

    由于 Smart QQ 从 2019 年 1 月 1 日起停止服务,所以该项目也已经停止维护了!

    35 引用 • 468 回帖 • 761 关注
  • Openfire

    Openfire 是开源的、基于可拓展通讯和表示协议 (XMPP)、采用 Java 编程语言开发的实时协作服务器。Openfire 的效率很高,单台服务器可支持上万并发用户。

    6 引用 • 7 回帖 • 119 关注
  • Node.js

    Node.js 是一个基于 Chrome JavaScript 运行时建立的平台, 用于方便地搭建响应速度快、易于扩展的网络应用。Node.js 使用事件驱动, 非阻塞 I/O 模型而得以轻量和高效。

    139 引用 • 269 回帖