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