4.4.1　通過方法遞歸實(shí)現(xiàn)階乘函數(shù)

編程里的方法概念有點(diǎn)類似數(shù)學(xué)中的函數(shù)，事實(shí)上，Java自帶的數(shù)學(xué)工具M(jìn)ath就集成了不少對應(yīng)的數(shù)學(xué)函數(shù)，包括開方函數(shù)sqrt、冪函數(shù)pow、取整函數(shù)round、正弦函數(shù)sin、余弦函數(shù)cos等。可是Math工具只提供了一些基本的數(shù)學(xué)函數(shù)，仍有許多數(shù)學(xué)函數(shù)未能提供，比如階乘函數(shù)（n!=1*2*3*...*n）就不支持。對于這些系統(tǒng)尚不支持的數(shù)學(xué)運(yùn)算，只要可以用程序代碼描述它們的算法，就能自己編寫專門的方法來實(shí)現(xiàn)對應(yīng)的函數(shù)功能。

仍以階乘函數(shù)為例，按照該函數(shù)的定義，n!=1*2*3*...*n，顯然運(yùn)算結(jié)果是1～n這一串連續(xù)自然數(shù)的乘積，該算法很適合采用循環(huán)語句實(shí)現(xiàn)。先聲明一個結(jié)果變量result和一個整型變量i，令result與i的初始值都為1，接著每次循環(huán)都給i加1，并將result賦值為自身乘以i的運(yùn)算結(jié)果，直到i等于n為止。也可令result與i的初始值都為n，接著每次循環(huán)都給i減1，并將result賦值為自身乘以i的運(yùn)算結(jié)果，直到i等于1為止。按此思路編寫的循環(huán)方式計(jì)算階乘函數(shù)的示例代碼如下（完整代碼見本章源碼的src\com\method\RecursionFactorial.java）：

    // 利用循環(huán)語句實(shí)現(xiàn)階乘函數(shù)n!
    private static long factorialRepeat(int n) {
        long result=n;
        for (int i=n - 1; i > 1; i--) {
            result=result * i;  // 只要i大于1，就乘上它
        }
        return result;
    }

考慮到n!=n×(n-1)!，等式右邊的(n-1)!同樣是一個階乘函數(shù)，區(qū)別在于輸入?yún)?shù)由n變?yōu)榱?i>n-1，并且n大于1時都存在階乘運(yùn)算(n-1)!，只有n值減少到1的時候，才不再需要計(jì)算(n-1)!。像n!=n×(n-1)!，然后(n-1)!=(n-1)×(n-2)!這般反復(fù)調(diào)用函數(shù)自身的情況，被稱作函數(shù)的遞歸調(diào)用。它包含兩個方面的含義：一方面是遞進(jìn)調(diào)用自身方法，直到滿足某個條件后結(jié)束自身調(diào)用；另一方面是逐次回歸到上一個調(diào)用處，從剛才提到的條件位置開始返回，攜帶輸出參數(shù)一路回到最初的方法調(diào)用。遞歸手段把一個復(fù)雜的問題轉(zhuǎn)化為規(guī)模較小的相似問題，達(dá)到一定條件后將問題消弭于無形當(dāng)中，可謂“大事化小、小事化了”，因而它比常規(guī)的循環(huán)語句要節(jié)省代碼。

依據(jù)遞歸調(diào)用的算法思想，可將前述的階乘方法代碼改寫為如下的遞歸方式代碼：

    // 利用方法遞歸實(shí)現(xiàn)階乘函數(shù)n!
    private static long factorialRecursion(int n) {
if (n <= 1) {  // n小于等于1，結(jié)束遞歸
            return n;
        } else {  // 若n是一個大于1的整數(shù)，則重復(fù)遞歸調(diào)用
            return n * factorialRecursion(n - 1);
        }
    }

可見采用遞歸手段之后，原方法內(nèi)部的for循環(huán)被消除掉了，只剩下簡單的if分支語句。注意到上面的分支代碼由單行的if/else語句組成，那么借助于三元運(yùn)算符“?:”可進(jìn)一步簡化代碼，簡化后的階乘方法代碼如下：

    // 利用三元運(yùn)算符“?:”簡化階乘函數(shù)n!
    private static long factorialSimplify(int n) {
        return (n <= 1) ? n : n * factorialSimplify(n - 1);
    }

這下有了自定義的階乘方法，外部僅需以下一行代碼，即可獲得階乘函數(shù)的運(yùn)算結(jié)果：

        int n=20;
        // 注意：使用long類型，階乘方法只能計(jì)算到“20!”，再往上面計(jì)算只能癲狂了
        long resultLong=factorialSimplify(n);
        System.out.println(n+"!的長整數(shù)階乘結(jié)果="+resultLong);

運(yùn)行以上的階乘代碼，觀察到下面的輸出日志：

20!的長整數(shù)階乘結(jié)果=2432902008176640000

由于目前的階乘方法使用long類型保存運(yùn)算結(jié)果，而long類型的表達(dá)范圍只有-2⁶³~2⁶³-1，因此該階乘方法最多只能計(jì)算到20!，若讓它計(jì)算21!，則階乘結(jié)果超出long類型的表達(dá)能力，導(dǎo)致階乘方法無法返回正確的結(jié)果數(shù)字。真是沒想到，原本以為long類型能夠表示高達(dá)19位的整數(shù)范圍，用作平常的整數(shù)運(yùn)算理應(yīng)不在話下，不料僅僅一個21!就讓long類型不堪重負(fù)，看來基本變量類型并不適合高級的科學(xué)運(yùn)算。

幸虧Java另外提供了大整數(shù)類型BigInteger，使用BigInteger可以表達(dá)任意大小的整數(shù)，只要計(jì)算機(jī)內(nèi)存吃得消就行。引入大整數(shù)之后，原先的階乘方法可改寫為如下的代碼邏輯：

    // 利用大數(shù)字實(shí)現(xiàn)精確計(jì)算的階乘方法
    private static BigInteger factorialBig(int n) {
        BigInteger bigN=BigInteger.valueOf(n);  // 把整型的n轉(zhuǎn)換為大整數(shù)類型
        return (n <= 1) ? bigN : bigN.multiply(factorialBig(n - 1));
    }

外部依然按照原方式調(diào)用階乘方法，只是把輸入的參數(shù)值改為100，表示準(zhǔn)備計(jì)算100!。此時的調(diào)用代碼如下：

        int n=100;
        // 使用大數(shù)字類型，階乘方法可以一直計(jì)算下去，計(jì)算到“1000!”都沒問題
        BigInteger resultBig=factorialBig(n);
        System.out.println(n+"!的大整數(shù)階乘結(jié)果="+resultBig);

運(yùn)行上述的階乘代碼，觀察到下面的輸出日志，可見有了大整數(shù)的襄助，再大的整數(shù)運(yùn)算也不怕了。

100!的大整數(shù)階乘結(jié)果=9332621544394415268169923885626670049071596826438162146859296 3895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000