Java学习之递归

水深无声 2022-11-09 14:09 110阅读 0赞

**一、基本知识**

我们知道，当一个复杂的问题需要简化时，我们就会想到递归的使用。递归是解决复杂问题的一种常用方法。递归的基本思想是将复杂问题逐步分解成简单问题，最后实现问题的求解。

比如求解ｎ阶乘，

n! = n * (n-1)!;//n > 0

按照上述的定义，我们要想求解出n！，只要先求出(n-1)!，然后将其结果乘以n即可。同理，要想求解出(n-1)!，只需求解出(n-2)!，当n=0时，其阶乘为1。如此下来，n!的问题就简化到求解(n-1)!的问题了，应用这个思想，n可以一直递减到0。

众所周知，Java语言支持方法的递归调用，方法的递归调用其实就是方法自己调用自己。

下面，我们设计一个程序计算n!，将递归方法设为factor(n)。

**程序效果图：**

![在这里插入图片描述][20210315163423980.png_pic_center]

**Java代码：**

public class DiGuiJieCheng {
        
    	public static long factor(int n) {
        
    		if(n == 0)
    			return 1;
    		else
    			return n * factor(n-1);//if-else循环实现递归
    	}
    	public static void main(String[] args) {
        
    	int k = 20;
    	System.out.println(k + "!=" + factor(k));
    	System.out.println("long型最大值=" + Long.MAX_VALUE);//long型数的最大值
    	}
    }

**小结：**

1.上述程序用到的factor(n)的描述如下：

if(n == 0)
    			return 1;
    		else
    			return n * factor(n-1);//if-else循环实现递归

2.如果n>20，那么的值将将超出long型数据的范围，此时运行得不到正确的结果。所以，当我们需要求解较大数的阶乘时，可以使用java.math包中BigInteger类，BigInteger类拓展了Number类并实现了接口，它的实例可以表示任何大小的整数且不可变。

下面有一个使用BigInteger类计算50！的案例：

**程序效果图：**

![在这里插入图片描述][20210315164912962.png_pic_center]

**Java代码：**

import java.math.*;
    public class BigInter_50JieCheng {
        
    	public static BigInteger factorial(long n) {
        
    		BigInteger result = BigInteger.ONE;//BigInter.ONE常量表示1
    		for(long i = 1; i <= n; i++) {
        
    			result = result.multiply(new BigInteger(i+""));
    		}
    		return result;
    	}
    	public static void main(String[] args) {
        
    	System.out.println("50!=" + factorial(50));
    	}
    }

[20210315163423980.png_pic_center]: /images/20221023/3f0c517de9af45afac18a3abc41c593f.png
[20210315164912962.png_pic_center]: /images/20221023/5117163482e24df685d8a1b77b618772.png