深度递归必须知道的尾调用(Lambda)
引导语
本文从一个递归栈溢出说起，像大家介绍一下如何使用尾调用解决这个问题，以及尾调用的原理，最后还提供一个解决方案的工具类，大家可以在工作中放心用起来。
递归-发现栈溢出
现在我们有个需求，需要计算任意值阶乘的结果，阶乘我们用 n！表示，它的计算公式是：n! = 123……(n-1)n，比如说 3 的阶乘就是 123。
对于这个问题，我们首先想到的应该就是递归，我们立马写了一个简单的递归代码：
// 阶乘计算
public static String recursion(long begin, long end, BigDecimal total) {
// begin 每次计算时都会递增，当 begin 和 end 相等时，计算结束，返回最终值
if (begin == end) {
return total.toString();
}
// recursion 第三个参数表示当前阶乘的结果
return recursion(++begin, end, total.multiply(new BigDecimal(begin)));
}递归代码很简单，我们写了一个简单的测试，如下：
@Test
public void testRecursion() {
log.info("计算 10 的阶乘，结果为{}",recursion(1, 10, BigDecimal.ONE));
}运行结果很快就出来了，结果为：3628800，是正确的。
因为需求是能够计算任意值，接着我们把 10 换成 9000，来计算一下 9000 的阶乘，可这时却突然报错了，报错的信息如下：
StackOverflowError 是栈溢出的异常，jvm 给栈分配的大小是固定的，方法本身的定义、入参、方法里的局部变量这些都会占内存，随着递归不断进行，递归的方法就会越来越多，每个方法都能从栈中得到内存，渐渐的，栈的内存就不够了，报了这个异常。
我们首先想到的办法是如何让栈的内存大一点呢？JVM 有个参数叫做 -Xss，这个参数就规定了要分配给栈多少大小的内存，于是我们在 idea 里面配置一下 Xss 的参数，配置如下：
图中我们给栈分配 200k 大小内存，再次运行仍然报错，说明我们分配的栈还是太小了，于是我们修改 Xss 值到 100M 试一下，配置如下：
再次运行，成功了，运行结果如下：
虽然通过修改栈的大小暂时解决了这个问题，但这种解决方案在线上是完全行不通的，主要问题如下：
-
我们不可能修改线上栈的大小，一般来说，线上栈的大小一般都是 256k，不可能为了一个递归程序把栈大小修改成很大。
-
因为我们需要计算任意值的阶乘，所以栈的大小是动态的，即使我们修改成 100m 的话，也难以保证递归时一定不会超出栈的深度。
那该怎么办呢，有木有其他办法可以解决这个问题呢？在想其他办法之前，我们先思考下问题的根源在那里。
每次递归时，栈都会给递归的方法分配内存，递归深度越深，方法就会越多，内存分配就会越多，而且递归执行的时候，是递归到最后一层的时候，递归才会真正执行，也就是说在没有递归到最后一层时，所有被分配的递归方法都无法执行，所有栈内存也都无法被释放，这样就导致栈的内存很快被消耗完，我们画一个图简单释义一下：
我们知道了问题根源后，突然发现有一种技术很适合解决这种问题：尾调用。
尾调用
尾调用主要是用来解决递归时，栈溢出的问题，不需要任何改造，只需要在代码的最后一行返回无任何计算的递归代码，编译器就会自动进行优化，比如之前写的递归代码，我们修改成如下即可：
public static BigDecimal recursion1(long begin, long end, BigDecimal total) {
if (begin == end) {
return total;
}
++begin;
total = total.multiply(new BigDecimal(begin));
return recursion1(begin, end, total);//在方法的最后直接返回，叫做尾调用
}上面代码方法的最后一行直接返回递归的代码，并且没有任何计算逻辑，这样子编译器会自动识别，并解决栈溢出的问题。
但 Java 是不支持的，只有 C 语言才支持！！！
但我们立马又想到了 Java 8 中的新技术可以解决这个问题：Lambda。
尾调用的 Lambda 实现
首先我们必须先介绍一下 Lambda 的特性，Lambda 的方法分为两种，懒方法和急方法，网上通俗的说明是懒方法是不会执行的，只有急方法才会执行，本文用到的特性就是懒方法不执行，懒方法不执行的潜在含义是：方法只是申明出来了，栈不会给方法分配内存，如果用到递归上，那么不管递归多少次，栈只会给每个递归递归分配一个 Lambda 包装的递归方法声明变量而已，并不会给递归方法分配内存。
我们画一张图释义一下：
接着我们代码实现以下：
- 首先我们实现了一个尾调用的接口，方便大家使用：
// 尾调用的接口，定义了是否完成，执行等方法
public interface TailRecursion<T> {
TailRecursion<T> apply();
default Boolean isComplete() {
return Boolean.FALSE;
}
default T getResult() {
throw new RuntimeException("递归还没有结束，暂时得不到结果");
}
default T invoke() {
return Stream.iterate(this, TailRecursion::apply)
.filter(TailRecursion::isComplete)
.findFirst()
.get()//执行急方法
.getResult();
}
}- 接着实现了利用这个接口实现 9k 的阶乘，代码如下：
public class TestDTO {
private Long begin;
private Long end;
private BigDecimal total;
}
public static TailRecursion<BigDecimal> recursion1(TestDTO testDTO) {
// 如果已经递归到最后一个数字了，结束递归，返回 testDTO.getTotal() 值
if (testDTO.getBegin().equals(testDTO.getEnd())) {
return TailRecursionCall.done(testDTO.getTotal());
}
testDTO.setBegin(1+testDTO.getBegin());
// 计算本次递归的值
testDTO.setTotal(testDTO.getTotal().multiply(new BigDecimal(testDTO.getBegin())));
// 这里是最大的不同，这里每次调用递归方法时，使用的是 Lambda 的方式，这样只是初始化了一个 Lambda 变量而已，recursion1 方法的内存是不会分配的
return TailRecursionCall.call(()->recursion1(testDTO));
}- 最后我们写了一个测试方法，我们把栈的大小设定成 200k，测试代码如下：
public void testRecursion1(){
TestDTO testDTO = new TestDTO();
testDTO.setBegin(1L);
testDTO.setEnd(9000L);
testDTO.setTotal(BigDecimal.ONE);
log.info("计算 9k 的阶乘，结果为{}",recursion1(testDTO).invoke());
}最终运行的结果如下：
从运行结果可以看出，虽然栈的大小只有 200k，但利用 Lambda 懒加载的特性，却能轻松的执行 9000 次递归。
总结
我们写递归的时候，最担心的就是递归深度过深，导致栈溢出，而使用 Lambda 尾调用的机制却可以完美解决这个问题，所以赶紧用起来吧。