深度递归必须知道的尾调用(Lambda)

作者: bbsmax 发布时间: 2019-09-10 浏览: 1804 次 编辑

引导语

本文从一个递归栈溢出说起,像大家介绍一下如何使用尾调用解决这个问题,以及尾调用的原理,最后还提供一个解决方案的工具类,大家可以在工作中放心用起来。

递归-发现栈溢出

现在我们有个需求,需要计算任意值阶乘的结果,阶乘我们用 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 试一下,配置如下:

再次运行,成功了,运行结果如下:

虽然通过修改栈的大小暂时解决了这个问题,但这种解决方案在线上是完全行不通的,主要问题如下:

  1. 我们不可能修改线上栈的大小,一般来说,线上栈的大小一般都是 256k,不可能为了一个递归程序把栈大小修改成很大。

  2. 因为我们需要计算任意值的阶乘,所以栈的大小是动态的,即使我们修改成 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 包装的递归方法声明变量而已,并不会给递归方法分配内存。

我们画一张图释义一下:

接着我们代码实现以下:

  1. 首先我们实现了一个尾调用的接口,方便大家使用:

// 尾调用的接口,定义了是否完成,执行等方法
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();
  }
}
  1. 接着实现了利用这个接口实现 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));
}
  1. 最后我们写了一个测试方法,我们把栈的大小设定成 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 尾调用的机制却可以完美解决这个问题,所以赶紧用起来吧。