好好学Java：从零基础到项目实战
上QQ阅读APP看书，第一时间看更新
上一章目录下一章

4.4.1　通过方法递归实现阶乘函数

编程里的方法概念有点类似数学中的函数，事实上，Java自带的数学工具Math就集成了不少对应的数学函数，包括开方函数sqrt、幂函数pow、取整函数round、正弦函数sin、余弦函数cos等。可是Math工具只提供了一些基本的数学函数，仍有许多数学函数未能提供，比如阶乘函数（n!=1*2*3*...*n）就不支持。对于这些系统尚不支持的数学运算，只要可以用程序代码描述它们的算法，就能自己编写专门的方法来实现对应的函数功能。

仍以阶乘函数为例，按照该函数的定义，n!=1*2*3*...*n，显然运算结果是1～n这一串连续自然数的乘积，该算法很适合采用循环语句实现。先声明一个结果变量result和一个整型变量i，令result与i的初始值都为1，接着每次循环都给i加1，并将result赋值为自身乘以i的运算结果，直到i等于n为止。也可令result与i的初始值都为n，接着每次循环都给i减1，并将result赋值为自身乘以i的运算结果，直到i等于1为止。按此思路编写的循环方式计算阶乘函数的示例代码如下（完整代码见本章源码的src\com\method\RecursionFactorial.java）：

    // 利用循环语句实现阶乘函数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)!同样是一个阶乘函数，区别在于输入参数由n变为了n-1，并且n大于1时都存在阶乘运算(n-1)!，只有n值减少到1的时候，才不再需要计算(n-1)!。像n!=n×(n-1)!，然后(n-1)!=(n-1)×(n-2)!这般反复调用函数自身的情况，被称作函数的递归调用。它包含两个方面的含义：一方面是递进调用自身方法，直到满足某个条件后结束自身调用；另一方面是逐次回归到上一个调用处，从刚才提到的条件位置开始返回，携带输出参数一路回到最初的方法调用。递归手段把一个复杂的问题转化为规模较小的相似问题，达到一定条件后将问题消弭于无形当中，可谓“大事化小、小事化了”，因而它比常规的循环语句要节省代码。

依据递归调用的算法思想，可将前述的阶乘方法代码改写为如下的递归方式代码：

    // 利用方法递归实现阶乘函数n!
    private static long factorialRecursion(int n) {
if (n <= 1) {  // n小于等于1，结束递归
            return n;
        } else {  // 若n是一个大于1的整数，则重复递归调用
            return n * factorialRecursion(n - 1);
        }
    }

可见采用递归手段之后，原方法内部的for循环被消除掉了，只剩下简单的if分支语句。注意到上面的分支代码由单行的if/else语句组成，那么借助于三元运算符“?:”可进一步简化代码，简化后的阶乘方法代码如下：

    // 利用三元运算符“?:”简化阶乘函数n!
    private static long factorialSimplify(int n) {
        return (n <= 1) ? n : n * factorialSimplify(n - 1);
    }

这下有了自定义的阶乘方法，外部仅需以下一行代码，即可获得阶乘函数的运算结果：

        int n=20;
        // 注意：使用long类型，阶乘方法只能计算到“20!”，再往上面计算只能癫狂了
        long resultLong=factorialSimplify(n);
        System.out.println(n+"!的长整数阶乘结果="+resultLong);

运行以上的阶乘代码，观察到下面的输出日志：

20!的长整数阶乘结果=2432902008176640000

由于目前的阶乘方法使用long类型保存运算结果，而long类型的表达范围只有-263~263-1，因此该阶乘方法最多只能计算到20!，若让它计算21!，则阶乘结果超出long类型的表达能力，导致阶乘方法无法返回正确的结果数字。真是没想到，原本以为long类型能够表示高达19位的整数范围，用作平常的整数运算理应不在话下，不料仅仅一个21!就让long类型不堪重负，看来基本变量类型并不适合高级的科学运算。

幸亏Java另外提供了大整数类型BigInteger，使用BigInteger可以表达任意大小的整数，只要计算机内存吃得消就行。引入大整数之后，原先的阶乘方法可改写为如下的代码逻辑：

    // 利用大数字实现精确计算的阶乘方法
    private static BigInteger factorialBig(int n) {
        BigInteger bigN=BigInteger.valueOf(n);  // 把整型的n转换为大整数类型
        return (n <= 1) ? bigN : bigN.multiply(factorialBig(n - 1));
    }

外部依然按照原方式调用阶乘方法，只是把输入的参数值改为100，表示准备计算100!。此时的调用代码如下：

        int n=100;
        // 使用大数字类型，阶乘方法可以一直计算下去，计算到“1000!”都没问题
        BigInteger resultBig=factorialBig(n);
        System.out.println(n+"!的大整数阶乘结果="+resultBig);

运行上述的阶乘代码，观察到下面的输出日志，可见有了大整数的襄助，再大的整数运算也不怕了。

100!的大整数阶乘结果=9332621544394415268169923885626670049071596826438162146859296 3895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
上一章目录下一章