递归是一种强大且有魅力的解决问题的方式。它具有很强的表现力 —— 使用递归，我们可以通过将相同的解决方案应用于子问题来解决问题，这种方法被称为分治法。各种应用都会采用递归，例如在地图上寻找最短距离、计算最小成本或最大利润，或者减少浪费。

如今使用的大多数语言都支持递归。不幸的是，真正能从递归中受益的问题往往规模较大，简单的实现很快就会导致栈溢出。在本文中，我们将探讨尾调用优化（TCO）技术，使递归适用于大规模输入。然后，我们将研究可以用高度递归且有重叠的解决方案来表达的问题，并探讨如何使用记忆化技术让它们的执行速度大幅提升。

使用尾调用优化

使用递归的最大障碍是处理大规模输入时存在栈溢出的风险。出色的尾调用优化技术可以消除这个顾虑。尾调用是一种递归调用，其中最后执行的操作是对自身的调用。这与常规递归不同，在常规递归中，函数除了调用自身外，还常常会对递归调用的结果进行进一步的计算。尾调用优化让我们可以将常规递归调用转换为尾调用，使递归在处理大规模输入时变得可行。

Java 在编译器层面并不直接支持尾调用优化，但我们可以使用 Lambda 表达式用几行代码来实现它。通过这种有时被称为蹦床调用的解决方案，我们可以享受递归的强大功能，而不必担心栈溢出。

我们将使用一个非常简单且常见的例子 —— 计算一个数的阶乘来实现尾调用优化。

从非优化的递归开始

让我们从一段使用简单的非优化递归计算阶乘的代码开始。

1: public class Factorial {2: public static int factorialRec(final int number) {3: if(number == 1) {4: return number;5: }6:7: return number * factorialRec(number - 1);8: }9: }

当递归到值为 1 时，递归终止。对于更大的值，我们递归地调用当前数字乘以该数字减 1 的阶乘。让我们用数字 5 来测试这个方法。

System.out.println(factorialRec(5));

以下是阶乘值的输出：

120

看起来可行，但让我们再试一次，这次使用一个更大的输入值。

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

我们对这个调用进行了防御性编码，让我们看看输出结果如何。

java.lang.StackOverflowError

递归无法处理大规模输入。它以失败告终。这是采用这种强大且富有表现力的技术的一个阻碍。

问题不在于递归本身，而是在等待递归完成的过程中保留了部分计算结果。让我们仔细看看 factorialRec 方法中的第 7 行。在那一行上，我们执行的最后一个操作是乘法（*）。在保留给定数字的同时，我们等待下一次对 factorialRec 的调用结果返回。因此，每次调用都会增加调用栈的深度，如果输入规模不断增大，代码执行最终会导致栈溢出。我们需要一种不依赖栈的递归方式。

在《计算机程序的构造和解释》[AS96] 中，Abelson 和 Sussman 讨论了尾调用优化技术，他们在底层将递归转换为纯粹的迭代。理想情况下，我们希望依赖编译器来提供这样的优化，但由于 Java 编译器不支持，我们可以使用 Lambda 表达式手动实现，接下来我们将看到具体实现。

转向尾递归

在使用尾调用优化技术之前，我们必须重新设计代码，使其不会导致栈深度不断增加。我们可以不再等待在 factorialRec 方法的第 7 行执行乘法，而是计算到目前为止的部分积，并将其作为额外参数传递给后续调用。这样，当从递归调用返回时，就不需要执行任何算术运算了。这是很好的第一步，但还不够。此外，在递归调用方法之前，我们必须从当前栈级别返回。换句话说，我们需要将对 factorialRec 的立即调用转换为延迟调用。为此，我们将使用 TailCall 函数式接口和配套的 TailCalls 类。我们很快会设计这两个类，但现在先假设它们已经存在。

首先，让我们对 TailCalls 类的方法进行静态导入。

import static fpij.TailCalls.done;import static fpij.TailCalls.call;

我们将在新的递归版本 factorialTailRec 方法中使用这两个方法来计算阶乘。

public static TailCall<Integer> factorialTailRec( final int factorial, final int number) { if (number == 1) { return done(factorial); } return call(() -> factorialTailRec(factorial * number, number - 1));}

这个计算阶乘的版本是尾递归的，即最后一个操作是对自身的（延迟/惰性）调用，并且返回时不需要对结果进行进一步的计算。而且，我们没有立即调用 factorialTailRec 方法，而是将其包装在 Lambda 表达式中，以便延迟执行。

创建 TailCall 函数式接口

当我们调用 factorialTailRec 方法时，它会立即返回一个 TailCall 实例。这里的关键思想是，如果我们调用 done 方法，就表示递归终止。另一方面，如果我们调用 call 方法，就表示需要继续递归，但要先从当前栈级别返回。为了完全理解其工作原理，我们必须深入研究这些方法，所以让我们深入研究 TailCall 接口和 TailCalls 配套类。我们从接口开始。

@FunctionalInterfacepublic interface TailCall<T> { TailCall<T> 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 方法简单地返回 false 值。result 方法的默认实现如果被调用会抛出错误 —— 只要递归还在进行，我们就不会调用这个方法；当递归终止时，TailCall 接口的另一种实现会处理这种情况。

关键的工作在 invoke 方法的简短代码中完成。这个方法与 apply 方法协作，apply 方法将返回下一个等待执行的 TailCall 实例。invoke 方法有两个职责。首先，它必须反复迭代待处理的 TailCall 递归，直到到达递归的末尾。其次，到达末尾后，它必须返回最终结果（可在终端 TailCall 实例的 result 方法中获取）。

invoke 方法虽然简短，但其中有很多操作，所以让我们放慢速度深入研究。

我们不知道会有多少次递归调用；它不是无限的，但我们可以将其视为一个长度未知的序列。一旦我们把它当作一个 TailCall 对象序列，就可以轻松地对挂起的 TailCall 实例流进行惰性迭代。我们在“创建无限的延迟集合”中使用的技术将帮助我们在这里惰性地生成下一个挂起的 TailCall 实例。让我们仔细看看具体实现。

为了创建一个挂起的 TailCall 实例的惰性列表，我们使用 Stream 接口的 iterate 静态方法。这个方法接受一个初始种子值和一个生成器。我们使用当前的 TailCall 实例 this 作为种子。生成器是一个 UnaryOperator，它接受当前元素并生成下一个元素。为了让生成器返回下一个挂起的 TailCall 实例，它可以使用当前 TailCall 的 apply 方法。为此，我们使用方法引用 TailCall::apply 来创建生成器。

简而言之，我们设计 invoke 方法，使迭代从种子（第一个 TailCall 实例）开始，遍历生成器生成的后续 TailCall 实例，直到找到一个表示递归终止的 TailCall 实例。

创建 TailCalls 便利类

迭代会一直持续，直到 isComplete 方法报告完成。但 TailCall 接口中该方法的默认实现总是返回 false 值。这就是配套的 TailCalls 类发挥作用的地方。它为 TailCall 函数式接口提供了两种不同的实现：一种在 call 方法中，另一种在 done 方法中。

public class TailCalls { public static <T> TailCall<T> call(final TailCall<T> nextCall) { return nextCall; } public static <T> TailCall<T> done(final T value) { return new TailCall<T>() { @Override public boolean isComplete() { return true; } @Override public T result() { return value; } @Override public TailCall<T> apply() { throw new Error("not implemented"); } }; }}

在这个类中，我们实现了两个静态方法 call 和 done。call 方法简单地接收一个 TailCall 实例并将其传递下去。这是一个便利方法，这样递归调用（如 factorialTailRec）可以对称地以对 done 或 call 的调用结束。

在 done 方法中，我们返回一个专门的 TailCall 版本来表示递归的终止。在这个方法中，我们将接收到的值包装在专门实例的重写 result 方法中。专门版本的 isComplete 方法将通过返回 true 值来报告递归的结束。最后，apply 方法抛出一个异常，因为在这个表示递归结束的终端 TailCall 实现中，这个方法永远不会被调用。

从这个设计中我们可以看到，通过 call 返回的 TailCall 会继续递归，而从 done 返回的 TailCall 会终止递归。此外，递归调用在 invoke 默认方法的循环中都是惰性求值的，因此不会像简单递归那样增加栈深度。

我们设计 TailCall 和 TailCalls 是为了与 factorialTailRec 一起使用，但它们可以用于任何尾递归函数。

使用尾递归函数

我们已经看到了尾递归函数 factorialTailRec、函数式接口 TailCall 和便利类 TailCalls。让我们通过一个场景来了解它们是如何协同工作的。

让我们从调用 factorialTailRec 来计算 2 的阶乘开始，如下所示：

factorialTailRec(1, 2).invoke();

第一个参数 1 是阶乘的初始值；第二个参数 2 是我们要计算阶乘的数字。对 factorialTailRec 的调用会检查给定的数字是否等于 1，由于不等于，它会使用 call 方法并传递一个合成 TailCall 实例的 Lambda 表达式。

这个合成实例会惰性地调用 factorialTailRec，并分别传入两个参数 2 和 1。回到 factorialTailRec 方法调用之外，对 invoke 方法的调用会以这个第一个 TailCall 实例为种子创建一个惰性集合，并探索这个集合，直到收到一个终止的 TailCall 实例。当种子 TailCall 的 apply 方法被调用时，会导致对 factorialTailRec 的调用，传入我们之前提到的两个参数。

对 factorialTailRec 的第二次调用会导致对 done 方法的调用。

对 done 方法的调用会返回一个终止的专门 TailCall 实例，表明递归终止。invoke 方法现在将返回计算的最终结果，在这个例子中是 2。

阶乘递归的尾调用优化完成了。让我们测试一下 factorialTailRec 方法。我们先使用一个小的输入参数值来调用它。

System.out.println(factorialTailRec(1, 5).invoke());

我们用初始阶乘值 1 和数字作为种子调用 factorialTailRec。这个调用的结果是一个 TailCall 实例，我们对它调用 invoke 方法。这个调用的结果应该与我们之前看到的非优化递归版本相同。

120

让我们用大的输入值运行这个版本。

System.out.println(factorialTailRec(1, 20000).invoke());

之前的版本遇到了栈溢出问题。让我们看看这个版本的结果。

0

我们的努力得到了回报。我们避免了栈溢出，但由于算术溢出，结果为 0；阶乘结果是一个非常大的数。我们很快会解决这个问题 —— 我们需要使用 BigInteger 而不是 int。在解决这个问题之前，让我们回顾一下这个解决方案。我们需要进行一些清理工作。

清理递归实现

factorialTailRec 的实现非常简单诱人。不过，它有一个缺点：我们污染了方法的接口。现在我们不再是传递一个简单的输入数字，而是必须传递两个参数。我们依赖调用者为第一个参数提供 1；像 0 这样的参数会使结果出错。我们还必须对 factorialTailRec 调用的结果调用 invoke 方法 —— 这并不方便。我们可以通过引入一层额外的间接性轻松解决这些问题。

我们可以将 factorialTailRec 变成一个私有方法，并引入一个调用它的公共方法。

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

这个方法恢复了简单的接口，并封装了尾递归的细节。它处理了额外的参数，并在最后调用了必要的 invoke 方法。让我们使用这个修改后的版本。

System.out.println(factorial(5));System.out.println(factorial(20000));

我们用一个小值和一个非常大的值运行了最新版本；让我们看看输出结果。

1200

小值的结果是正确的，但大值的结果需要修复。让我们作为最后一步来处理这个问题。

修复算术溢出问题

使用 int 基本类型的阶乘代码简洁明了。为了避免算术溢出，我们必须切换到 BigInteger。遗憾的是，我们将失去像 * 和 - 这样简单算术运算符的流畅性，必须使用 BigInteger 的方法来执行这些操作。我们将在 BigFactorial 类中为这些操作创建小函数，以减少代码的混乱。

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"); //...}

我们编写了一些便利方法和字段来处理 BigInteger。现在让我们看看重要的部分，即封装的尾递归函数和围绕它的流畅包装器。

private static TailCall<BigInteger> factorialTailRec( final BigInteger factorial, final BigInteger number) { if(number.equals(BigInteger.ONE)) { return done(factorial); } return call(() -> factorialTailRec(multiply(factorial, number), decrement(number)));}public static BigInteger factorial(final BigInteger number) { return factorialTailRec(BigInteger.ONE, number).invoke();}

在早期版本中我们使用 int 的地方，在这个版本中我们使用 BigInteger。代码的其余部分基本相同，使用了 TailCall 接口、TailCalls 类和尾调用优化技术。

让我们调用这个修改后的 factorial 版本。

public static void main(final String[] args) { System.out.println(factorial(FIVE)); System.out.println(String.format("%.10s...", factorial(TWENTYK)));}

现在我们使用了 BigInteger，操作应该会顺利进行。

1201819206320...

我们看到了数字 5 的阶乘的正确值，以及大输入的截断输出值。

多亏了 Lambda 表达式、函数式接口和无限流，我们只用了几行代码就将非优化的递归转换为尾递归，并避免了栈溢出。

有了这种技术，我们可以大胆地实现递归解决方案，只需进行一些小的重新设计，将它们转换为尾调用

利用记忆化技术加速

快速回答，25 * 12 等于多少？ 除非你有超能力，否则你需要花些精力和时间才能得出结果 300。现在，如果我马上再问你 25 * 12 等于多少，你会立刻给出答案 300。你怎么变得这么快？嗯，你记住了结果，暂时把它记在了脑子里 —— 或者我们应该说你对它进行了记忆化处理。

如果你最近计算过一个表达式或查找过一些信息，而你又需要这些信息时，你很可能会从记忆中提取细节，而不是重复这项任务。但计算机在这方面比我们高效得多。复用计算结果而不是重复计算，这种技术叫做记忆化。这在递归问题中特别有用，因为递归问题的解决方案中包含多个具有相同解的子问题。

让我们看看记忆化如何将过度递归的问题转化为执行速度极快的问题。我们将探讨一个问题，用递归实现它，并注意随着问题规模的增大，它的执行速度是如何呈指数级下降的。然后我们将使用记忆化技术来加速它，并在此过程中了解 Lambda 表达式如何帮助解决问题。

一个优化问题

我们可以在各个领域看到优化问题，比如经济学、金融学和资源分配领域，在这些领域中需要从多个可行的解决方案中选择一个最优解。例如，我们可能需要从资产销售中找到最大利润，或者找到不同地点之间的最短路线。在一种叫做动态规划的算法技术中，我们广泛使用递归来解决问题。这将递归提升到了一个新的层次；问题的解决方案与子问题的解决方案存在重叠。

如果我们简单地实现这样的递归，随着输入规模的增加，计算所需的时间会呈指数级增长。这就是记忆化技术发挥作用的地方。在这种技术中，如果解决方案已经存在，我们就直接查找，并且只对计算进行一次执行和存储。反复请求重叠解决方案时存在的冗余不会转化为重新计算，而是转化为对结果的快速查找。这种技术将指数级的时间复杂度转化为了线性时间复杂度。让我们用一个例子来实现这一点：钢条切割问题 [15]。

我们将为一家以批发价购买钢条并以零售价出售的公司提供解决方案。他们发现，通过将钢条切割成不同的尺寸，可以实现利润最大化。该公司对不同长度钢条的定价经常变化，所以公司希望我们编写一个程序，揭示对于给定长度的钢条，最大利润是多少。让我们先找到一个简单的解决方案，然后再对其进行改进。

我们先创建一个类来存储不同长度钢条的价格。

public class RodCutter { private final List<Integer> prices; public RodCutter(final List<Integer> pricesForLengths) { prices = pricesForLengths; } //...}

让我们使用一些从 1 英寸开始的不同长度钢条的示例价格。

final List<Integer> priceValues = Arrays.asList(2, 1, 1, 2, 2, 2, 1, 8, 9, 15);final RodCutter rodCutter = new RodCutter(priceValues);普通递归

我们可以使用简单的递归解决这个问题。如果给我们一根 5 英寸的钢条，我们可以查找该长度的价格。在这个例子中，这会让我们得到 2 美元。我们可以做得更好 —— 毕竟，一根 4 英寸的钢条也能卖 2 美元，所以我们可以把这根钢条切成两段 —— 4 英寸和 1 英寸 —— 以增加利润。

按照这种方法继续，我们发现对于任意长度 n 的钢条，最大利润是该长度所有可能的 2^(n - 1) 种切割方式所获得的利润中的最大值。也就是说，对于给定长度 n，最大利润是 max(不切割, 切割(1, n - 1), 切割(2, n - 2), …)。下图是一根 5 英寸钢条所有可能切割方式的利润示例。

为了计算 5 英寸钢条的最大利润，我们需要计算 4 英寸、3 英寸、2 英寸和 1 英寸钢条的最大利润。同样，为了计算 4 英寸钢条的最大利润，我们需要计算更小尺寸钢条的最大利润。这个解决方案巧妙地引入了重叠递归；我们先不进行任何优化来实现它，然后再对其进行改进。

让我们实现计算最大利润的逻辑。

public int maxProfit(final int length) { int priceAtLength = length <= prices.size() ? prices.get(length - 1) : 0; return Math.max(priceAtLength, IntStream.range(1, length) .map(i -> maxProfit(i) + maxProfit(length - i)) .max() .orElse(0));}

在 maxProfit 方法中，我们查找特定长度的价格。然后，我们递归地找出所有相加等于给定长度的切割方式的利润，并从中选择最大值。

实现结果很简单。让我们对几个长度进行测试。

System.out.println(rodCutter.maxProfit(5));System.out.println(rodCutter.maxProfit(22));

让我们看看不同长度的输出结果。

1044

输出结果似乎合理，但计算这个结果需要几分钟时间。如果我们将长度稍微从 22 增加一点，程序会慢很多，甚至需要几个小时。这是因为这个计算的时间复杂度是指数级的 —— O(2^(n - 1)) —— 我们对各种长度进行了冗余计算。我们需要对结果进行记忆化处理，以大幅加快执行速度。

记忆化结果

记忆化是一种简单而巧妙的技术，可以让递归重叠计算变得快速。使用这种技术，程序运行时，只有在计算还未进行时才进行计算。每次进行新的计算时，我们都会缓存结果，并在后续对相同输入的调用中复用这些结果。只有当对于给定输入，计算每次都期望返回相同的结果时，这种技术才有用。我们的钢条切割问题符合这一期望：对于给定的长度和给定的价格集，无论我们询问多少次，利润都是相同的。让我们对利润计算的结果进行记忆化处理。

在计算某个子长度的利润时，如果该长度的利润已经计算过，我们就可以跳过计算。这将加快程序的速度，因为查找利润的冗余调用将变成对哈希表的快速查找。听起来不错，但如果有可复用的代码就更好了。让我们创建一个可复用的类，我们将其称为 Memoizer。它目前还不存在，但我们先假设它存在并编写使用它的代码。让我们重构 maxProfit 方法，以使用 Memoizer 类的静态方法 callMemoized。

public int maxProfit(final int length) { return callMemoized(this::computeMaxProfit, length);}private int computeMaxProfit( Function<Integer, Integer> memoizedFunction, int length) { int priceAtLength = length <= prices.size() ? prices.get(length - 1) : 0; return Math.max(priceAtLength, IntStream.range(1, length) .map(i -> memoizedFunction.apply(i) + memoizedFunction.apply(length - i)) .max() .orElse(0));}

在深入研究代码之前，让我们先看看设计的关键部分。我们创建了一个函数 computeMaxProfit，并对其进行记忆化处理。经过记忆化处理的版本会在调用实际实现之前先查找值。让我们讨论一下我们是如何实现这一点的。

在 maxProfit 方法中，我们调用（尚未实现的）Memoizer 类的 callMemoized 方法。我们将对 computeMaxProfit 方法的方法引用作为第一个参数传递给这个函数，并将我们要计算最大利润的钢条长度作为第二个参数传递。

computeMaxProfit 方法接受两个参数 —— 第一个是对经过记忆化处理的函数的引用，第二个是我们要计算最大利润的长度。在 computeMaxProfit 方法中，我们执行任务，当需要递归时，我们将调用路由到 memoizedFunction，即经过记忆化处理的函数引用。如果该值已经被缓存或记忆化，这将快速返回结果。否则，它将递归地将调用路由到 computeMaxProfit 方法，以计算该长度的利润。当我们看到 callMemoized 方法时，我们将全面了解这是如何实现的。

谜题中缺失的部分是如何从传递给 callMemoized 方法的参数创建经过记忆化处理的函数。让我们看看 Memoizer 类的实现，以更好地理解这一点。

public class Memoizer { public static <T, R> R callMemoized( final BiFunction<Function<T,R>, T, R> functionToMemoize, final T input) { Function<T, R> memoizedFunction = new Function<T, R>() { private final Map<T, R> store = new HashMap<>(); public R apply(final T input) { if(!store.containsKey(input)) { store.put(input, functionToMemoize.apply(this, input)); } return store.get(input); } }; return memoizedFunction.apply(input); }}

Memoizer 类只有一个简短的函数。在 callMemoized 方法中，我们创建了一个 Function 的实现，在其中我们检查给定输入的解决方案是否已经存在于 store 哈希表中。如果给定输入的值已经存在，我们就返回它；否则，我们计算给定输入的值，将其存储在 store 哈希表中，并返回计算得到的值。

这个版本的 maxProfit 方法很好地封装了记忆化的细节。对这个方法的调用看起来与之前的版本相同：

System.out.println(rodCutter.maxProfit(5));System.out.println(rodCutter.maxProfit(22));

让我们运行经过记忆化处理的版本，并确保报告的最大利润与之前的版本相同。

1044

两个版本的利润是一致的，但执行速度却有天壤之别。经过记忆化处理的版本耗时不到 0.05 秒，而之前的版本则需要几分钟。有了这个经过记忆化处理的版本，我们可以轻松地将钢条长度增加到很大的值，并且仍然只需要不到一秒的时间就能得到结果。例如，500 英寸的钢条对执行时间没有任何影响；它的速度非常快。

在本文中，我们使用 Lambda 表达式和无限流实现了尾调用优化和记忆化。这些例子向我们展示了 Java 中的特性如何结合起来创建强大的解决方案。你可以使用类似的技术为自己的复杂问题创建巧妙的解决方案。

总结

递归是编程中的一个有价值的工具，但简单的递归实现通常对实际问题并不实用。函数式接口、Lambda 表达式和无限流可以帮助我们设计尾调用优化，使递归在这种情况下变得可行。我们还可以将递归和记忆化结合起来，使重叠递归的执行速度加快。

在下一篇中，我们将探索一个使用 Lambda 表达式的实际示例，然后轻松地对其进行并行化处理。