JAVA中使用递归和尾递归实现1000的阶乘

 1 import java.math.BigInteger;
 2 
 3 public class Main {
 4 
 5     public static void main(String[] args) {
 6         long t = System.currentTimeMillis();
 7         System.out.println(factorial(new BigInteger("1000")));
 8         System.out.println(System.currentTimeMillis()- t);
 9         t = System.currentTimeMillis();
10         System.out.println(factorial2(new BigInteger("1000"),BigInteger.ONE));
11         System.out.println(System.currentTimeMillis()- t);
12     }
13 
14 
15     /**
16      * 使用线性递归计算阶乘
17      * @param n
18      * @return
19      */
20     public static BigInteger factorial(BigInteger n ){
21         if (n.compareTo(BigInteger.ZERO) < 0) return BigInteger.ZERO;
22 
23         if (n.equals(BigInteger.ONE) || n.equals(BigInteger.ZERO)) {
24             return new BigInteger("1");
25         }
26         return n.multiply(factorial(n.subtract(BigInteger.ONE)));
27     }
28 
29 
30     /**
31      * 使用尾递归计算阶乘
32      * 如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。
33      * 当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。
34      * 尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。
35      * 尾递归是极其重要的，不用尾递归，函数的堆栈耗用难以估量，需要保存很多中间函数的堆栈。
36      * 通过参数传递结果，达到不压栈的目的
37      * @param n
38      * @param result
39      * @return
40      */
41     public static BigInteger factorial2(BigInteger n,BigInteger result){
42         if (n.compareTo(BigInteger.ZERO) < 0) return BigInteger.ZERO;
43 
44         if (n.equals(BigInteger.ONE) || n.equals(BigInteger.ZERO)) {
45             return result;
46         }
47 
48         return  factorial2(n.subtract(BigInteger.ONE),n.multiply(result));
49     }
50 
51 }

402387260077093773543702433923003985719374864210714632543799910...（太长了,省略）000
38

402387260077093773543702433923003985719374864210714632543799910...（省略）000
11

Process finished with exit code 0