目录

函数式的思考

本章内容

  • 为什么要进行函数式编程
  • 什么是函数式编程
  • 声明式编程以及引用透明性
  • 编写函数式Java的准则
  • 迭代和递归

你已经发现了,本书中频繁地出现“函数式”这个术语。到目前为止,你可能也对函数式编 程包含哪些内容有了一定的了解。它指的是Lambda表达式和一等函数吗?还是说限制你对可变对象的修改?如果是这样,采用函数式编程能为你带来什么好处呢?这一章中,我们会一一为你 解答这些问题。我们会介绍什么是函数式编程,以及它的一些术语。我们首先会探究函数式编程背后的概念,比如副作用不变性声明式编程引用透明性,并将它们和Java 8的实践相结合。 下一章,我们会更深入地研究函数式编程的工作,包括高阶函数、科里化、持久化数据结构、延 迟列表、模式匹配以及结合器。

实现和维护系统

让我们假设你被要求对一个大型的遗留软件系统进行升级,而且这个系统你之前并不是非常 了解。你是否应该接受维护这种软件系统的工作呢?稍有理智的外包Java程序员只会依赖如下这种言不由衷的格言做决定,“搜索一下代码中有没有使用synchronized关键字,如果有就直接 拒绝(由此我们可以了解修复并发导致的缺陷有多困难),否则进一步看看系统结构的复杂程度”。我们会在下面中提供更多的细节,但是你发现了吗,正如我们在前面几章所讨论的,如果你喜欢 无状态的行为(即你处理Stream的流水线中的函数不会由于需要等待从另一个方法中读取变量(写读), 或者由于需要写入的变量同时有另一个方法正在写而发生中断(写写)),Java 8中新增的Stream提供了 强大的工作支撑,让我们无需担心锁引起的各种问题,充分发掘系统的并发能力。

为了让程序易于使用,你还希望它具备哪些特性呢?你会希望它具有良好的结构,最好类的结构应该反映出系统的结构,这样能便于大家理解;甚至软件工程中还提供了指标,对结构的合理性进行评估,比如耦合性(软件系统中各组件之间是否相互独立)以及内聚性(系统的各相关部分之间如何协作)

不过,对大多数程序员而言,最关心的日常要务是代码维护时的调试:代码遭遇一些无法预 期的值就有可能发生崩溃。为什么会发生这种情况?它是如何进入到这种状态的?想想看你有多 少代码维护的顾虑都能归咎到这一类! 很明显,函数式编程提出的“无副作用”以及“不变性” 对于解决这一难题是大有裨益的。让我们就此展开进一步的探讨。

共享的可变数据

最终,我们刚才讨论的无法预知的变量修改问题,都源于共享的数据结构被你所维护的代码 中的多个方法读取和更新。假设几个类同时都保存了指向某个列表的引用。那么到底谁对这个列 表拥有所属权呢?如果一个类对它进行了修改,会发生什么情况?其他的类预期会发生这种变化 吗?其他的类又如何得知列表发生了修改呢?我们需要通知使用该列表的所有类这一变化吗? 抑或是不是每个类都应该为自己准备一份防御式的数据备份以备不时之需呢?换句话说,由于使用了可变的共享数据结构,我们很难追踪你程序的各个组成部分所发生的变化。图13-1解释了这 一问题。

https://gitee.com/lienhui68/picStore/raw/master/null/20200815132048.png

假设有这样一个系统,它不修改任何数据。维护这样的一个系统将是一个无以伦比的美梦, 因为你不再会收到任何由于某些对象在某些地方修改了某个数据结构而导致的意外报告。如果一 个方法既不修改它内嵌类的状态,也不修改其他对象的状态,使用return返回所有的计算结果, 那么我们称其为纯粹的或者无副作用的。

更确切地讲,到底哪些因素会造成副作用呢?简而言之,副作用就是函数的效果已经超出了 函数自身的范畴。下面是一些例子。

  • 除了构造器内的初始化操作,对类中数据结构的任何修改,包括字段的赋值操作(一个典型的例子是setter方法)。
  • 抛出一个异常。
  • 进行输入/输出操作,比如向一个文件写数据。

从另一个角度来看“无副作用”的话,我们就应该考虑不可变对象。不可变对象是这样一种 对象,它们一旦完成初始化就不会被任何方法修改状态。这意味着一旦一个不可变对象初始化完毕,它永远不会进入到一个无法预期的状态。你可以放心地共享它,无需保留任何副本,并且由于它们不会被修改,还是线程安全的。

“无副作用”这个想法的限制看起来很严苛,你甚至可能会质疑是否有真正的生产系统能够 以这种方式构建。我们希望结束本章的学习之后,你能够确信这一点。一个好消息是,如果构成系统的各个组件都能遵守这一原则,该系统就能在完全无锁的情况下,使用多核的并发机制,因 为任何一个方法都不会对其他的方法造成干扰。此外,这还是一个让你了解你的程序中哪些部分 是相互独立的非常棒的机会。

这些思想都源于函数式编程,我们在下一节会进行介绍。但是在开始之前,让我们先看看函数式编程的基石——声明式编程吧。

声明式编程

一般通过编程实现一个系统,有两种思考方式。一种专注于如何实现,比如:“首先做这个, 紧接着更新那个,然后……”举个例子,如果你希望通过计算找出列表中最昂贵的交易,通常需 要执行一系列的命令:从列表中取出一个交易,将其与临时最昂贵交易进行比较;如果该交易开 销更大,就将临时最昂贵的交易设置为该交易;接着从列表中取出下一个交易,并重复上述操作。

这种“如何做”风格的编程非常适合经典的面向对象编程,有些时候我们也称之为命令式编程,因为它的特点是它的指令和计算机底层的词汇非常相近,比如赋值、条件分支以及循环, 就像下面这段代码:

1
2
3
4
5
6
7
8
Transaction mostExpensive = transactions.get(0);
        if (mostExpensive == null) throw new IllegalArgumentException("Empty list of transactions")

        for (Transaction t : transactions.subList(1, transactions.size())) {
            if (t.getValue() > mostExpensive.getValue()) {
                mostExpensive = t;
            }
        }

另一种方式则更加关注要做什么。你在第4章和第5章中已经看到,使用Stream API你可以指 定下面这样的查询:

1
2
Optional<Transaction> mostExpensive = transactions.stream()
                .max(comparing(Transaction::getValue));

这个查询把最终如何实现的细节留给了函数库。我们把这种思想称之为内部迭代。它的巨大 优势在于你的查询语句现在读起来就像是问题陈述,由于采用了这种方式,我们马上就能理解它的功能,比理解一系列的命令要简洁得多。

采用这种“要做什么”风格的编程通常被称为声明式编程。你制定规则,给出了希望实现的 目标,让系统来决定如何实现这个目标。它带来的好处非常明显,用这种方式编写的代码更加接 近问题陈述了。

为什么要采用函数式编程

函数式编程具体实践了前面介绍的声明式编程(“你只需要使用不相互影响的表达式,描述 想要做什么,由系统来选择如何实现”)和无副作用计算。正如我们前面所讨论的,这两个思想能帮助你更容易地构建和维护系统

同时也请注意,我们在第3章中使用Lambda表达式介绍的内容,即一些语言的特性,比如构造操作和传递行为对于以自然的方式实现声明式编程是必要的,它们能让我们的程序更便于阅 读,易于编写。你可以使用Stream将几个操作串接在一起,表达一个复杂的查询。这些都是函数式编程语言的特性;我们在14.5节中介绍结合器时会更加深入地介绍这些内容。

为了让你有更直观的感受,我们会结合Java 8语言的新特性介绍这些,现在我们会具体给出函数式编程的定义,以及它在Java语言中的表述。我们希望表达的是,使用函数式编程,你可以实现更加健壮的程序,还不会有任何的副作用

什么是函数式编程

对于“什么是函数式编程”这一问题最简化的回答是“它是一种使用函数进行编程的方式”。 那什么是函数呢?

我们很容易想象这样一个方法,它接受一个整型和一个浮点型参数,返回一个浮点型的结 果——它也有副作用,随着调用次数的增加,它会不断地更新共享变量,如图13-2所示。

https://gitee.com/lienhui68/picStore/raw/master/null/20200815134427.png

在函数式编程的上下文中,一个“函数”对应于一个数学函数:它接受零个或多个参数,生 成一个或多个结果,并且不会有任何副作用。你可以把它看成一个黑盒,它接收输入并产生一些 输出,如图13-3所示。

https://gitee.com/lienhui68/picStore/raw/master/null/20200815134514.png

这种类型的函数和你在Java编程语言中见到的函数之间的区别是非常重要的(我们无法想象,log或者sin这样的数学函数会有副作用)。尤其是,使用同样的参数调用数学函数,它所返回的结果一定是相同的。这里,我们暂时不考虑Random.nextInt这样的方法,稍后我们会在介 绍引用透明性时讨论这部分内容。

当谈论“函数式”时,我们想说的其实是“像数学函数那样——没有副作用”。由此,编程 上的一些精妙问题随之而来。我们的意思是,每个函数都只能使用函数和像if-then-else这样 的数学思想来构建吗?或者,我们也允许函数内部执行一些非函数式的操作,只要这些操作的结 果不会暴露给系统中的其他部分?换句话说,如果程序有一定的副作用,不过该副作用不会为其他的调用者感知,是否我们能假设这种副作用不存在呢?调用者不需要知道,或者完全不在意这 些副作用,因为这对它完全没有影响。

当我们希望能界定这二者之间的区别时,我们将第一种称为纯粹的函数式编程(在本章的最 后会讨论这部分内容),后者称为函数式编程

函数式Java编程

编程实战中,你是无法用Java语言以纯粹的函数式来完成一个程序的。比如,Java的I/O模型 就包含了带副作用的方法(调用Scanner.nextLine就有副作用,它会从一个文件中读取一行, 通常情况两次调用的结果完全不同)。不过,你还是有可能为你系统的核心组件编写接近纯粹函数式的实现。在Java语言中,如果你希望编写函数式的程序,首先需要做的是确保没有人能觉察到你代码的副作用,这也是函数式的含义。假设这样一个函数或者方法,它没有副作用,进入方 法体执行时会对一个字段的值加一,退出方法体之前会对该字段减一。对一个单线程的程序而言, 这个方法是没有副作用的,可以看作函数式的实现。换个角度而言,如果另一个线程可以查看该 字段的值——或者更糟糕的情况,该方法会同时被多个线程并发调用——那么这个方法就不能称 之为函数式的实现了。当然,你可以用加锁的方式对方法的方法体进行封装,掩盖这一问题,你 甚至可以再次声称该方法符合函数式的约定。但是,这样做之后,你就失去了在你的多核处理器 的两个核上并发执行两个方法调用的能力。它的副作用对程序可能是不可见的,不过对于程序员 你而言是可见的,因为程序运行的速度变慢了!

我们的准则是,被称为“函数式”的函数或方法都只能修改本地变量。除此之外,它引用的对象都应该是不可修改的对象。通过这种规定,我们期望所有的字段都为final类型,所有的引用类型字段都指向不可变对象。后续的内容中,你会看到我们实际也允许对方法中全新创建的对象中的字段进行更新,不过这些字段对于其他对象都是不可见的,也不会因为保存对后续调用结果造成影响。

我们前述的准则是不完备的,要成为真正的函数式程序还有一个附加条件,不过它在最初时不太为大家所重视。要被称为函数式,函数或者方法不应该抛出任何异常。关于这一点,有 一个极为简单而又极为教条的解释:你不应该抛出异常,因为一旦抛出异常,就意味着结果被终止了;不再像我们之前讨论的黑盒模式那样,由return返回一个恰当的结果值。不过,这一 规则似乎又和我们实际的数学使用有冲突:虽然合法的数学函数为每个合法的参数值返回一个 确定的结果,很多通用的数学操作在严格意义上称之为局部函数式(partial function)可能更为 妥当。这种函数对于某些输入值,甚至是大多数的输入值都返回一个确定的结果;不过对另一 些输入值,它的结果是未定义的,甚至不返回任何结果。这其中一个典型的例子是除法和开平 方运算,如果除法的第二操作数是0,或者开平方的参数为负数就会发生这样的情况。以Java那 样抛出一个异常的方式对这些情况进行建模看起来非常自然。这里存在着一定的争执,有的作 者认为抛出代表严重错误的异常是可以接受的,但是捕获异常是一种非函数式的控制流,因为 这种操作违背了我们在黑盒模型中定义的“传递参数,返回结果”的规则,引出了代表异常处 理的第三支箭头,如图13-4所示。

https://gitee.com/lienhui68/picStore/raw/master/null/20200815135627.png

那么, 如果不使用异常, 你该如何对除法这样的函数进行建模呢?答案是请使用 Optional<T>类型:你应该避免让sqrt使用double sqrt(double)这样的函数签名,因为这 种方式可能抛出异常;与之相反我们推荐你使用Optional<Double> sqrt(double)——这种 方式下,函数要么返回一个值表示调用成功,要么返回一个空对象,表明其无法进行指定的操作。 当然,这意味着调用者需要检查方法返回的是否为一个空的Optional对象。这件事听起来代价不小,依据我们之前对函数式编程和纯粹的函数式编程的比较,从实际操作的角度出发,你可以选择在本地局部地使用异常,避免通过接口将结果暴露给其他方法,这种方式既取得了函数式的优点,又不会过度膨胀代码。

最后,作为函数式的程序,你的函数或方法调用的库函数如果有副作用,你必须设法隐藏它们的非函数式行为,否则就不能调用这些方法(换句话说,你需要确保它们对数据结构的任何修改对于调用者都是不可见的,你可以通过首次复制,或者捕获任何可能抛出的异常实现这一目 的)。 在13.2.4节中, 你会看到这样的例子, 我们通过复制列表的方式, 有效地隐藏了方法 insertAll调用库函数List.add所产生的副作用。

这些方法通常会使用注释或者使用标记注释声明的方式进行标注——符合我们规定的函数, 我们可以将其作为参数传递给并发流处理操作,比如我们在第4~7章介绍过的Stream.map方法。

为了各种各样的实战需求,你最终可能会发现即便对函数式的代码,我们还是需要向某些日志文件打印输出调试信息。是的,这意味着严格意义上说,这些代码并非函数式的,但是你已经在实际中享受了函数式程序带来的大多数好处

引用透明性

“没有可感知的副作用”(不改变对调用者可见的变量、不进行I/O、不抛出异常)的这些限 制都隐含着引用透明性。如果一个函数只要传递同样的参数值,总是返回同样的结果,那这个 函数就是引用透明的。String.replace方法就是引用透明的,因为像"raoul".replace(‘r’, ‘R’)这样的调用总是返回同样的结果(replace方法返回一个新的字符串,用小写的r替换掉 所有大写的R),而不是更新它的this对象,所以它可以被看成函数式的。

换句话说,函数无论在何处、何时调用,如果使用同样的输入总能持续地得到相同的结果, 就具备了函数式的特征。这也解释了我们为什么不把Random.nextInt看成函数式的方法。Java 语言中, 使用 Scanner 对象从用户的键盘读取输入也违反了引用透明性原则, 因为每次调用 nextLine时都可能得到不同的结果。不过,将两个final int类型的变量相加总能得到同样的结果,因为在这种声明方式下,变量的内容是不会被改变的。

引用透明性是理解程序的一个重要属性。它还包含了对代价昂贵或者需长时间计算才能得到结果的变量值的优化(通过保存机制而不是重复计算),我们通常将其称为记忆化或者缓存。虽然重要,但是现在讨论还是有些跑题,我们会在14.5节进行介绍。

Java语言中,关于引用透明性还有一个比较复杂的问题。假设你对一个返回列表的方法调用了两次。这两次调用会返回内存中的两个不同列表,不过它们包含了相同的元素。如果这些列表被当作可变的对象值(因此是不相同的),那么该方法就不是引用透明的。如果你计划将这些列表作为单纯的值(不可修改),那么把这些值看成相同的是合理的,这种情况下该方法是引用透明的。通常情况下,在函数式编程中,你应该选择使用引用透明的函数。我们会在14.5节继续讨 论这一主题。现在我们想探讨从更大的范围看是否应该修改对象的值。

面向对象编程和函数式编程的对比

我们由函数式编程和(极端)典型的面向对象编程的对比入手进行介绍,最终你会发现Java 8认为这些风格其实只是面向对象的一个极端。作为Java程序员,毫无疑问,你一定使用过某种函数式编程,也一定使用过某些我们称为极端面向对象的编程。正如我们在第1章中所介绍的那 样,由于硬件(比如多核)和程序员期望(比如使用类数据库查询式的语言去操纵数据)的变化, 促使Java的软件工程风格在某种程度上愈来愈向函数式的方向倾斜,本书的目的之一就是要帮助 你应对这种潮流的变化。

关于这个问题有两种观点。一种支持极端的面向对象:任何事物都是对象,程序要么通过更新字段完成操作,要么调用对与它相关的对象进行更新的方法。另一种观点支持引用透明的函数 式编程,认为方法不应该有(对外部可见的)对象修改。实际操作中,Java程序员经常混用这些 风格。你可能会使用包含了可变内部状态的迭代器遍历某个数据结构,同时又通过函数式的方式 (我们曾经讨论过,可以使用可变局部变量实现这一目标)计算数据结构中的变量之和。本章接下来的一节以及下一章中主要的内容都围绕这函数式编程的技巧展开,帮助你编写更加模块化, 更适应多核处理器的应用程序。这些技巧和思想会成为你编程武器库中的秘密武器

函数式编程实战

让我们从解决一个示例函数式的编程练习题入手:给定一个列表List<value>,比如{1, 4, 9},构造一个List<List<Integer>>,它的成员都是类表{1, 4, 9}的子集——我们暂时不考虑 元素的顺序。{1, 4, 9}的子集是{1, 4, 9}、{1, 4}、{1, 9}、{4, 9}、{1}、{4}、{9}以及{}

包括空子集在内,这样的子集总共有8个。每个子集都使用List<Integer>表示,这就是答案中期望的List<List<Integer>>类型。

通常新手碰到这个问题都会觉得无从下手,对于“{1, 4, 9}的子集可以划分为包含1和不包含1的两部分”也需要特别解释 。不包含1的子集很简单就是{4, 9}的各子集,包含1的子集可以通过将1插入到{4, 9}的各子集得到。这样我们就能利用Java,以一种简单、自然、自顶向下(递归)的函数式编程方式实现该程序了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
static List<List<Integer>> subsets(List<Integer> list) {
        // 如果输入为空,它就只包含 一个子集,既空列表自身
        if (list.isEmpty()) {
            List<List<Integer>> ans = new ArrayList<>();
            ans.add(Collections.emptyList());
            return ans;
        }

        Integer first = list.get(0);
        List<Integer> rest = list.subList(1, list.size());

        // 取出一个第一个元素first,找出剩余部分的所有子集并将其赋予subans。subans构成了结果的另外一半
        List<List<Integer>> subans = subsets(rest);
        // 另一半是 subans2 , 它包含了subans中的所有列表,但是经过调整,在每个列表的第一个元素之前添加了first
        List<List<Integer>> subans2 = insertAll(first, subans);
        // 将两个集合合并就是完整的子集集合
        return concat(subans, subans2);

    }

如果给出的输入是{1, 4, 9},程序最终给出的答案是

1
{{}, {9}, {4}, {4, 9}, {1}, {1, 9}, {1, 4}, {1, 4, 9}}

我们一起回顾下你已经完成了哪些工作。你假设缺失的方法insertAll和concat自身都是 函数式的,并依此推断你的subsets方法也是函数式的,因为该方法中没有任何操作会修改现有 的结构(如果你熟悉数学的话,你大概对此很熟悉,这就是著名的归纳法啊)。

现在,让我们看看如何定义insertAll方法。这是第一个可能出现的坑。假设你已经定义好 了insertAll,它会修改传递给它的参数。那么,该程序会以修改subans2同样的方式,错误地 修改subans,最终导致答案中莫名地包含了{1, 4, 9}的8个副本。与之相反,你可以像下面这样 实现insertAll的功能:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
static List<List<Integer>> insertAll(Integer first, List<List<Integer>> lists) {
        List<List<Integer>> result = new ArrayList<>();
        for (List<Integer> list : lists) {
            /*复制列表,从而使你有机会对其进行添加操作。即使底层是可变的,
            你也不应该复制底层的结构(不过Integer底层是不可变的)*/
            List<Integer> copyList = new ArrayList<>();
            copyList.add(first);
            copyList.addAll(list);
            result.add(copyList);
        }
        return result;
    }

注意到了吗?你现在已经创建了一个新的List,它包含了subans的所有元素。你聪明地利 用了 Integer 对象无法修改这一优势, 否则你需要为每个元素创建一个副本。 由于聚焦于让 insertAll像函数式那样地工作,你很自然地将所有的复制操作放到了insertAll中,而不是 它的调用者中。

最终,你还需要定义concat方法。这个例子中,我们提供了一个简单的实现,但是我们希 望你不要这样使用(我们展示这段代码的目的只是为了便于你比较不同的编程风格)。

1
2
3
4
static List<List<Integer>> concat(List<List<Integer>> a, List<List<Integer>> b) {
    a.addAll(b);
    return a;
}

建议你采用的是下面这种方式:

1
2
3
4
5
static List<List<Integer>> concat(List<List<Integer>> a, List<List<Integer>> b) {
    List<List<Integer>> r = new ArrayList<>(a);
    r.addAll(b);
    return r;
}

为什么呢?第二个版本的concat是纯粹的函数式。虽然它在内部会对对象进行修改(向列 表r添加元素),但是它返回的结果基于参数却没有修改任何一个传入的参数。与此相反,第一个 版本基于这样的事实, 执行完 concat(subans, subans2) 方法调用后, 没人需要再次使用 subans的值。对于我们定义的subsets,这的确是事实,所以使用简化版本的concat是个不错 的选择。不过,这也取决于你如何审视你的时间,你是愿意为定位诡异的缺陷费劲心机耗费时间 呢?还是花费些许的代价创建一个对象的副本呢?

无论你怎样解释这个不太纯粹的concat方法,“只会用于第一参数可以被强制覆盖的场景, 或者只会使用在这个subsets方法中,任何对subsets的修改都会遵照这一标准进行代码评审”,一旦将来的某一天,某个人发现这段代码的某些部分可以复用,并且似乎可以工作时,你未来调 试的梦魇就开始了。我们会在14.2节继续讨论这一问题。

请牢记:考虑编程问题时,采用函数式的方法,关注函数的输入参数以及输出结果(即你希 望做什么),通常比设计阶段的早期就考虑如何做、修改哪些东西要卓有成效得多。我们现在转 入介绍更深入的递归,它是函数式编程特别推崇的一种工作,能帮你更深刻地理解“做什么”这 一风格。

递归和迭代

纯粹的函数式编程语言通常不包含像while或者for这样的迭代构造器。为什么呢?因为这 种类型的构造器经常隐藏着陷阱,诱使你修改对象。比如,while循环中,循环的条件需要更新; 否则循环就一次都不会执行,要么就进入无限循环的状态。但是,很多情况下循环还是非常有用 的。我们在前面的介绍中已经声明过,如果没有人能感知的话,函数式也允许进行变更,这意味 着我们可以修改局部变量。我们在Java中使用的for-each循环,for(Apple a : apples { }如果用迭代器方式重写,代码如下:

1
2
3
4
5
6
Iterator<Apple> it = apples.iterator();
while (it.hasNext()) {

    Apple apple = it.next();
    // ... 
}

这并不是问题,因为改变发生时,这些变化(包括使用next方法对迭代器状态的改变以及 在 while 循环内部对 apple 变量的赋值)对于方法的调用方是不可见的。 但是, 如果使用 for-each循环,比如像下面这个搜索算法就会带来问题,因为循环体会对调用方共享的数据结 构进行修改:

1
2
3
4
5
6
7
public void searchForGold(List<String> l, Stats stats) {
    for (String s : l) {
        if ("gold".equals(s)) {
            stats.incrementFor("gold");
        }
    }
}

实际上,对函数式而言,循环体带有一个无法避免的副作用:它会修改stats对象的状态, 而这和程序的其他部分是共享的。

由于这个原因,纯函数式编程语言,比如Haskell直接去除了这样的带有副作用的操作!之 后你该如何编写程序呢?比较理论的答案是每个程序都能使用无需修改的递归重写,通过这种方式避免使用迭代。使用递归,你可以消除每步都需更新的迭代变量。一个经典的教学问题是用迭代的方式或者递归的方式(假设输入值大于1)编写一个计算阶乘的函数(参数为正数),代码列表如下。

迭代式的阶乘计算

1
2
3
4
5
6
7
static int factorialIterative(int n) {
    int r = 1;
    for (int i = 1; i <= n; i++) {
        r *= i;
    }
    return r;
}

递归式的阶乘计算

1
2
3
static long factorialRecursive(long n) {
    return n == 1 ? 1 : n * factorialRecursive(n - 1);
}

第一段代码展示了标准的基于循环的结构:变量r和i在每轮循环中都会被更新。第二段代码 以更加类数学的形式给出一个递归方法(方法调用自身)的实现。Java语言中,使用递归的形式 通常效率都更差一些,我们很快会讨论这方面的内容。

但是,如果你已经仔细阅读过本书的前面章节,一定知道Java 8的Stream提供了一种更加简 单的方式,用描述式的方法来定义阶乘,代码如下。

基于Stream的阶乘

1
2
3
static long factorialStreams(long n) {
    return LongStream.rangeClosed(1, n).reduce(1, (long a, long b) -> a * b);
}

现在,我们回来谈谈效率问题。作为Java的用户,相信你已经意识到函数式程序的狂热支持 者们总是会告诉你说,应该使用递归,摒弃迭代。然而,通常而言,执行一次递归式方法调用的 开销要比迭代执行单一机器级的分支指令大不少。为什么呢?每次执行factorialRecursive 方法调用都会在调用栈上创建一个新的栈帧,用于保存每个方法调用的状态(即它需要进行的乘 法运算),这个操作会一直指导程序运行直到结束。这意味着你的递归迭代方法会依据它接收的 输入成比例地消耗内存。这也是为什么如果你使用一个大型输入执行factorialRecursive方 法,很容易遭遇StackOverflowError异常。

这是否意味着递归百无一用呢?当然不是!函数式语言提供了一种方法解决这一问题:尾-调优化(tail-call optimization)。基本的思想是你可以编写阶乘的一个递归定义,不过递归调用发生在函数的最后(所以我们说调用发生在尾部)。这种新型的递归调用经过优化后执行的速度快很多。作为示例,下面是一个阶乘的“尾-递”(tail-recursive)定义。

基于“尾-递”的阶乘

1
2
3
4
5
6
7
static long factorialTailRecursive(long n) {
    return factorialHelper(1, n);
}

static long factorialHelper(long acc, long n) {
    return n == 1 ? acc : factorialHelper(acc * n, n - 1);
}

方法factorialHelper属于“尾-递”类型的函数,原因是递归调用发生在方法的最后。

关于尾递归一个通俗易懂的例子

// 尾递归,进入下一个函数不再需要上一个函数的环境了(可以复用上一个方法的栈桢),得出结果以后直接返回。 function story() { 从前有座山,山上有座庙,庙里有个老和尚,一天老和尚对小和尚讲故事 story() }

// 非尾递归,下一个函数结束以后此函数还有后续,所以必须保存本身的环境(新建栈桢)以供处理返回值。 function story() { 从前有座山,山上有座庙,庙里有个老和尚,一天老和尚对小和尚讲故事 story() 小和尚听了,找了块豆腐撞死了 }

这种形式的递归是非常有意义的,现在我们不需要在不同的栈帧上保存每次递归计算的中间值,编译器能够自行决定复用某个栈帧进行计算。实际上,在factorialHelper的定义中,立即数(阶乘计算的中间结果)直接作为参数传递给了该方法。再也不用为每个递归调用分配单独的栈帧用于跟踪每次递归调用的中间值——通过方法的参数能够直接访问这些值

图13-5和图13-6解释了使用递归和“尾-递”实现阶乘定义的不同。

https://gitee.com/lienhui68/picStore/raw/master/null/20200815151259.png

尾递归优化

为了解决递归的开销大问题,使用尾递归优化,具体分两步:

  1. 你把递归调用的形式写成尾递归的形式;
  2. 编译器碰到尾递归,自动按照某种特定的方式进行优化编译

为什么Java还不支持这种优化

有的说法是:JAVA编写组不实现尾递归优化是觉得麻烦又没有太大的必要,就懒得实现了(原话是:在日程表上,但是非常靠后),官方的建议是不使用递归,而是使用while循环,迭代,递推

坏消息是,目前Java还不支持这种优化。但是使用相对于传统的递归,“尾递”可能是更好 的一种方式,因为它为最终实现编译器优化开启了一扇门。很多的现代JVM语言,比如Scala和Groovy都已经支持对这种形式的递归的优化,最终实现的效果和迭代不相上下(它们的运行速 度几乎是相同的)。这意味着坚持纯粹函数式既能享受它的纯净,又不会损失执行的效率。

使用Java 8进行编程时,我们有一个建议,你应该尽量使用Stream取代迭代操作,从而避免变化带来的影响。此外,如果递归能让你以更精炼,并且不带任何副作用的方式实现算法,你就应该用递归替换迭代。实际上,我们看到使用递归实现的例子更加易于阅读,同时又易于实现和理解(比如,我们在前文中展示的子集的例子),大多数时候编程的效率要比细微的执行时间差 异重要得多。

这一节,我们讨论了函数式编程,但仅仅是初步介绍了函数式方法的思想——我们介绍的内 容甚至适用于最早版本的Java。接下来的一章,我们会讨论Java 8携眷着的一类函数具备了哪些 让人耳目一新的强大能力。

小结

下面是这一章中你应该掌握的关键概念。

  • 从长远看,减少共享的可变数据结构能帮助你降低维护和调试程序的代价。
  • 函数式编程支持无副作用的方法和声明式编程。
  • 函数式方法可以由它的输入参数及输出结果进行判断。
  • 如果一个函数使用相同的参数值调用,总是返回相同的结果,那么它是引用透明的。
  • 采用递归可以取得迭代式的结构,比如while循环。
  • 相对于Java语言中传统的递归,“尾-递”可能是一种更好的方式,它开启了一扇门,让我们有机会最终使用编译器进行优化。