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

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

原文链接

递归优化
很多算法都依赖于递归,典型的比如分治法(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 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3194 引用 • 8214 回帖 • 2 关注
  • Lambda
    24 引用 • 19 回帖

相关帖子

欢迎来到这里!

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

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

推荐标签 标签

  • 心情

    心是产生任何想法的源泉,心本体会陷入到对自己本体不能理解的状态中,因为心能产生任何想法,不能分出对错,不能分出自己。

    59 引用 • 369 回帖
  • Flutter

    Flutter 是谷歌的移动 UI 框架,可以快速在 iOS 和 Android 上构建高质量的原生用户界面。 Flutter 可以与现有的代码一起工作,它正在被越来越多的开发者和组织使用,并且 Flutter 是完全免费、开源的。

    39 引用 • 92 回帖 • 1 关注
  • SpaceVim

    SpaceVim 是一个社区驱动的模块化 vim/neovim 配置集合,以模块的方式组织管理插件以
    及相关配置,为不同的语言开发量身定制了相关的开发模块,该模块提供代码自动补全,
    语法检查、格式化、调试、REPL 等特性。用户仅需载入相关语言的模块即可得到一个开箱
    即用的 Vim-IDE。

    3 引用 • 31 回帖 • 116 关注
  • iOS

    iOS 是由苹果公司开发的移动操作系统,最早于 2007 年 1 月 9 日的 Macworld 大会上公布这个系统,最初是设计给 iPhone 使用的,后来陆续套用到 iPod touch、iPad 以及 Apple TV 等产品上。iOS 与苹果的 Mac OS X 操作系统一样,属于类 Unix 的商业操作系统。

    87 引用 • 139 回帖
  • 导航

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

    43 引用 • 177 回帖 • 3 关注
  • 电影

    这是一个不能说的秘密。

    122 引用 • 608 回帖 • 1 关注
  • Webswing

    Webswing 是一个能将任何 Swing 应用通过纯 HTML5 运行在浏览器中的 Web 服务器,详细介绍请看 将 Java Swing 应用变成 Web 应用

    1 引用 • 15 回帖 • 636 关注
  • 博客

    记录并分享人生的经历。

    273 引用 • 2388 回帖
  • PWL

    组织简介

    用爱发电 (Programming With Love) 是一个以开源精神为核心的民间开源爱好者技术组织,“用爱发电”象征开源与贡献精神,加入组织,代表你将遵守组织的“个人开源爱好者”的各项条款。申请加入:用爱发电组织邀请帖
    用爱发电组织官网:https://programmingwithlove.stackoverflow.wiki/

    用爱发电组织的核心驱动力:

    • 遵守开源守则,体现开源&贡献精神:以分享为目的,拒绝非法牟利。
    • 自我保护:使用适当的 License 保护自己的原创作品。
    • 尊重他人:不以各种理由、各种漏洞进行未经允许的抄袭、散播、洩露;以礼相待,尊重所有对社区做出贡献的开发者;通过他人的分享习得知识,要留下足迹,表示感谢。
    • 热爱编程、热爱学习:加入组织,热爱编程是首当其要的。我们欢迎热爱讨论、分享、提问的朋友,也同样欢迎默默成就的朋友。
    • 倾听:正确并恳切对待、处理问题与建议,及时修复开源项目的 Bug ,及时与反馈者沟通。不抬杠、不无视、不辱骂。
    • 平视:不诋毁、轻视、嘲讽其他开发者,主动提出建议、施以帮助,以和谐为本。只要他人肯努力,你也可能会被昔日小看的人所超越,所以请保持谦虚。
    • 乐观且活跃:你的努力决定了你的高度。不要放弃,多年后回头俯瞰,才会发现自己已经成就往日所仰望的水平。积极地将项目开源,帮助他人学习、改进,自己也会获得相应的提升、成就与成就感。
    1 引用 • 487 回帖 • 4 关注
  • 智能合约

    智能合约(Smart contract)是一种旨在以信息化方式传播、验证或执行合同的计算机协议。智能合约允许在没有第三方的情况下进行可信交易,这些交易可追踪且不可逆转。智能合约概念于 1994 年由 Nick Szabo 首次提出。

    1 引用 • 11 回帖
  • SVN

    SVN 是 Subversion 的简称,是一个开放源代码的版本控制系统,相较于 RCS、CVS,它采用了分支管理系统,它的设计目标就是取代 CVS。

    29 引用 • 98 回帖 • 687 关注
  • Unity

    Unity 是由 Unity Technologies 开发的一个让开发者可以轻松创建诸如 2D、3D 多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

    25 引用 • 7 回帖 • 138 关注
  • 招聘

    哪里都缺人,哪里都不缺人。

    188 引用 • 1057 回帖
  • Bug

    Bug 本意是指臭虫、缺陷、损坏、犯贫、窃听器、小虫等。现在人们把在程序中一些缺陷或问题统称为 bug(漏洞)。

    76 引用 • 1742 回帖 • 1 关注
  • Node.js

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

    139 引用 • 269 回帖 • 1 关注
  • MongoDB

    MongoDB(来自于英文单词“Humongous”,中文含义为“庞大”)是一个基于分布式文件存储的数据库,由 C++ 语言编写。旨在为应用提供可扩展的高性能数据存储解决方案。MongoDB 是一个介于关系数据库和非关系数据库之间的产品,是非关系数据库当中功能最丰富,最像关系数据库的。它支持的数据结构非常松散,是类似 JSON 的 BSON 格式,因此可以存储比较复杂的数据类型。

    90 引用 • 59 回帖 • 5 关注
  • 游戏

    沉迷游戏伤身,强撸灰飞烟灭。

    179 引用 • 818 回帖 • 1 关注
  • Solidity

    Solidity 是一种智能合约高级语言,运行在 [以太坊] 虚拟机(EVM)之上。它的语法接近于 JavaScript,是一种面向对象的语言。

    3 引用 • 18 回帖 • 429 关注
  • DevOps

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

    56 引用 • 25 回帖 • 5 关注
  • NGINX

    NGINX 是一个高性能的 HTTP 和反向代理服务器,也是一个 IMAP/POP3/SMTP 代理服务器。 NGINX 是由 Igor Sysoev 为俄罗斯访问量第二的 Rambler.ru 站点开发的,第一个公开版本 0.1.0 发布于 2004 年 10 月 4 日。

    315 引用 • 547 回帖 • 4 关注
  • OpenStack

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

    10 引用
  • Latke

    Latke 是一款以 JSON 为主的 Java Web 框架。

    71 引用 • 535 回帖 • 817 关注
  • H2

    H2 是一个开源的嵌入式数据库引擎,采用 Java 语言编写,不受平台的限制,同时 H2 提供了一个十分方便的 web 控制台用于操作和管理数据库内容。H2 还提供兼容模式,可以兼容一些主流的数据库,因此采用 H2 作为开发期的数据库非常方便。

    11 引用 • 54 回帖 • 666 关注
  • Angular

    AngularAngularJS 的新版本。

    26 引用 • 66 回帖 • 545 关注
  • 反馈

    Communication channel for makers and users.

    125 引用 • 929 回帖 • 265 关注
  • jQuery

    jQuery 是一套跨浏览器的 JavaScript 库,强化 HTML 与 JavaScript 之间的操作。由 John Resig 在 2006 年 1 月的 BarCamp NYC 上释出第一个版本。全球约有 28% 的网站使用 jQuery,是非常受欢迎的 JavaScript 库。

    63 引用 • 134 回帖 • 737 关注
  • CodeMirror
    1 引用 • 2 回帖 • 152 关注