Java 编程中的阶乘

今天我们来谈谈阶乘。这是程序员需要了解并同时能够使用它的最基本功能之一。那么让我们开始吧。n的阶乘是从1到n的所有自然数的乘积（乘法）的值，记为n！它看起来像什么：

1! =  1
2! =  1 * 2 = 2
3! =  1 * 2 * 3 = 6
4! =  1 * 2 * 3 * 4 = 24
5! =  1 * 2 * 3 * 4 * 5  = 120

还有一个小规则，对于 0：

!0  = 1

例如，如果我们想要得到阶乘差 6! 和 4！：

6!-4! = 1⋅2⋅3⋅4⋅5⋅6 - 1⋅2⋅3⋅4 = 720 - 24 = 696

让我们看一下 Java 中的情况，并了解计算阶乘的几种方法。

通常的解决方案

public static int getFactorial(int f) {
  int result = 1;
  for (int i = 1; i <= f; i++) {
     result = result * i;
  }
  return result;
}

没什么复杂的：我们使用接收到的数字作为循环的大小，在循环中我们乘以所有先前的数字，直到达到 f。主要是：

System.out.println(getFactorial(6) - getFactorial(4));

我们检查并得到期望的结果：696。

递归解法

递归是通过调用自身的方法来执行一些逻辑。这种方法称为递归。通常它由两部分组成：

1. 方法退出条件，达到该条件后，方法应停止调用自身并开始向上传递值。否则，我们将因调用自身方法而陷入无限循环，从而导致StackOverflowError。

2. 在给定情况下需要一些处理（逻辑）+调用自身，但具有不同的传入值。

今天我们理想的递归示例是求阶乘：

public static int getFactorial(int f) {
  if (f <= 1) {
     return 1;
  }
  else {
     return f * getFactorial(f - 1);
  }
}

我们设置当递归达到 1 时退出递归的条件。如果参数不为 1，则我们将当前值乘以下一次调用此方法的结果（其中我们发送当前值 -1）。

流解决方案

对于那些不了解流功能或想要刷新记忆的人，阅读本文将会很有用。

public static int getFactorial(int f) {
  if (f <= 1) {
     return 1;
  }
  else {
     return IntStream.rangeClosed(2, f).reduce((x, y) -> x * y).getAsInt();
  }
}

这里我们使用一个特殊的类 IntStream，它在处理来自 int 值的流时提供附加功能。为了创建这样的流，我们使用它的静态方法 rangeClosed，它创建从 2 到 f（含）的值，步长为 1。接下来，我们使用 reduce 方法组合所有值，即我们在其中展示如何我们想将它们结合起来。最后，我们使用 getAsInt 终端方法获取结果值。

使用大整数

在Java中， BigInteger类经常用来处理数字，尤其是BIG数字。毕竟，如果我们使用 int，那么在不丢失数据的情况下我们可以取的最大阶乘是 31，对于 long - 39。但是如果我们需要 100 的阶乘怎么办？让我们看看之前的解决方案，但使用的是 BigInteger。

通常的解决方案

public static BigInteger getFactorial(int f) {
  BigInteger result = BigInteger.ONE;
  for (int i = 1; i <= f; i++)
     result = result.multiply(BigInteger.valueOf(i));
  return result;
}

计数算法本质上是相同的，但这里我们使用 BigInteger 的功能： BigInteger.ONE - 将起始值设置为 1。 乘法 - 前一个阶乘值与当前数字之间的乘法。

递归解法

public static BigInteger getFactorial(int f) {
  if (f <= 1) {
     return BigInteger.valueOf(1);
  }
  else {
     return BigInteger.valueOf(f).multiply(getFactorial(f - 1));
  }
}

该解决方案的一般逻辑没有改变，只是添加了一些使用 BigInteger 的方法。

流解决方案

public static BigInteger getFactorial(int f) {
  if (f < 2) {
     return BigInteger.valueOf(1);
  }
  else {
     return IntStream.rangeClosed(2, f).mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get();
  }
}

本质上一切都是一样的，只不过是 BigInteger。在流中，我们现在有了 mapToObj 方法，通过该方法我们可以将 int 值转换为 BigInteger ，以便随后使用 multip 将它们相乘（好吧，我们添加了 get 来从Optional包装器中获取一个对象）。如果我们使用参数 100 运行这三个方法中的任何一个，那么我们将不会发生溢出，我们将得到：

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000