18.3　递归和迭代

18.3　递归和迭代

递归（recursion）是函数式编程特别推崇的一种技术，它能培养你思考要“做什么”的编程风格。纯粹的函数式编程语言通常不提供像while或者for这样的迭代结构。为什么呢？因为这种结构经常隐藏着陷阱，诱使你修改对象。比如，while循环中，循环条件需要不断更新，否则循环就一次都不执行，要么就陷入无限循环的状态。不过，很多时候循环还是非常有用的。前文的介绍中已经声明过，如果没人能感知的话，函数式也允许进行变更，这意味着可以修改局部变量。Java中使用的for-each循环，譬如for(Apple apple : apples { }，如果用迭代器方式重写，其代码如下：

Iterator<Apple> it = apples.iterator();
while (it.hasNext()) {
    Apple apple = it.next();
    // ...
}

这种转换没啥问题，因为这些变化（包括next方法对迭代器状态的改变，以及while循环内部对apple变量的赋值）对方法的调用方是不可见的。但是，如果使用for-each循环，比如下面这个搜索算法就会带来问题，因为循环体会对调用方共享的数据结构进行修改：

public void searchForGold(List<String> l, Stats stats){
    for(String s: l){
        if("gold".equals(s)){
            stats.incrementFor("gold");
        }
    }
}

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

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

代码清单 18-1　迭代式的阶乘计算

static long factorialIterative(long n) {
    long r = 1;
    for (int i = 1; i <= n; i++) {
        r *= i;
    }
    return r;
}

代码清单 18-2　递归式的阶乘计算

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

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

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

代码清单 18-3　基于Stream的阶乘

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

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

Exception in thread "main" java.lang.StackOverflowError

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

代码清单 18-4　基于“尾–递”的阶乘

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属于“尾–递”类型的函数，原因是递归调用发生在方法的最后。对比前文中factorialRecursive方法的定义，这个方法的最后一个操作是乘以n，从而得到递归调用的结果。

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

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

图 18-5　使用栈桢方式的阶乘的递归定义

图 18-6　阶乘的尾?递定义，这里它只使用了一个栈帧

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

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

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

18.3 递归和迭代