递归 - java实现

递归：指在当前方法内调用自己的这种现象。

概述

public static void a(){
    a();
}
1
2
3

递归：

• 直接递归：自己的方法调用自己。
• 间接递归：自己的方法调用别的方法，别的方法又调用自己。

案例

已知：f(x) = f(x-1) + 1 （恒等式）

已知：f(1) = 1

求： f(10) = ?

分析：
当x=5时，f(5) = f(5-1) + 1 = f(4) + 1，可发现如下规律：
f(5) = f(4) + 1
f(4) = f(3) + 1
f(3) = f(2) + 1
f(2) = f(1) + 1
f(1) = 1

//代码实现：
@Test
void test02() {
  //计算 f(10)
  int res = f(10);
  System.out.println("计算结果： f(10) = "+res);//计算结果： f(10) = 10
}
//递归：
public int f(int x){
  if(x == 1){
      return 1;
  }else {
      return f(x-1)+1;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

递归的三要素：

1. 递归的公式。 f(x) = f(x-1) + 1
2. 递归的终结点。f(1) = 1
3. 递归的方向必须走向终结点。

递归累和

计算1 ~ n的和

分析：num的累和 = num + (num-1)的累和，所以可以把累和的操作定义成一个方法，递归调用。

实现代码：

public class DiGuiDemo {
	public static void main(String[] args) {
		//计算1~num的和，使用递归完成
		int num = 5;
      	// 调用求和的方法
		int sum = getSum(num);
      	// 输出结果
		System.out.println(sum);
		
	}
  	/*
  	  通过递归算法实现.
  	  参数列表:int 
  	  返回值类型: int 
  	*/
	public static int getSum(int num) {
      	/* 
      	   num为1时,方法返回1,
      	   相当于是方法的出口,num总有是1的情况
      	*/
		if(num == 1){
			return 1;
		}
      	/*
          num不为1时,方法返回 num +(num-1)的累和
          递归调用getSum方法
        */
		return num + getSum(num-1);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

小贴士：递归一定要有条件限定，保证递归能够停止下来，次数不要太多，否则会发生栈内存溢出。

递归求阶乘

• 阶乘：所有小于及等于该数的正整数的积。

n的阶乘：n! = n * (n-1) *...* 3 * 2 * 1 
1

分析：这与累和类似,只不过换成了乘法运算，学员可以自己练习，需要注意阶乘值符合int类型的范围。

推理得出：n! = n * (n-1)!
1

代码实现：

public class DiGuiDemo {
  	//计算n的阶乘，使用递归完成
    public static void main(String[] args) {
        int n = 3;
      	// 调用求阶乘的方法
        int value = getValue(n);
      	// 输出结果
        System.out.println("阶乘为:"+ value);
    }
	/*
  	  通过递归算法实现.
  	  参数列表:int 
  	  返回值类型: int 
  	*/
    public static int getValue(int n) {
      	// 1的阶乘为1
        if (n == 1) {
            return 1;
        }
      	/*
      	  n不为1时,方法返回 n! = n*(n-1)!
          递归调用getValue方法
      	*/
        return n * getValue(n - 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

问题

递归其实是有开销的，而且使用不当，可能会出现意外的结果，比如说这个调用：

System.out.println(getValue(100000));//StackOverflowError
1

系统并不会给出任何结果，而会抛出异常。

优化

递归函数经常可以转换为非递归的形式，通过循环实现。比如，求阶乘的例子，其非递归形式的定义是：

n! = 1 × 2 × 3 × … × n
1

这个可以用循环来实现，代码如下：

//使用for循环，计算阶乘
public long getValue2(int n){
    long result = 1;
    for (int i=1;i<=n;i++){
        result = result * i;
    }
    return result;
}
//使用 BigDecimal 优化
public BigDecimal getValue3(int n){
    BigDecimal result = BigDecimal.valueOf(1);
    for (int i=1;i<=n;i++){
        result = result.multiply(BigDecimal.valueOf(i));
    }
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

递归啤酒问题

非规律化递归问题。

啤酒问题：啤酒2元一瓶，4个盖子可以换一瓶，2个空瓶（无盖子）可以换一瓶。

/**
 * 啤酒问题：啤酒2元一瓶，4个盖子可以换一瓶，2个空瓶（无盖子）可以换一瓶。
 */
@Test
void mytest(){
    int i = 0;
    while (true){
        System.out.println("------------------------------- start - "+(++i)+" ---------------------------------");
        System.out.println("啤酒问题：啤酒2元一瓶，4个盖子可以换一瓶，2个空瓶（无盖子）可以换一瓶。");
        System.out.print("请输入购买金额：");
        int money;
        try {
            Scanner sc = new Scanner(System.in);
            money = sc.nextInt();
            if(money <= 0) {//输入小于等于0的数，退出系统
                System.err.println("bye bye!");
                break;
            }
            totalNums = lastEmptyBottleNums = lastLidNums = 0;//重置系统参数
            buyBeer(money);
            System.out.println(money+"元可以喝到【"+totalNums+"】瓶酒。");
            if(money % 2 > 0){
                System.out.println("找回零钱："+money % 2+"元");
            }
            System.out.println("剩下的空瓶数量："+lastEmptyBottleNums);
            System.out.println("剩下的盖子数量："+lastLidNums);
            System.out.println("------------------------------- end - "+i+" ---------------------------------");
            System.out.println("\n\n");
        }catch (Exception e){
            System.err.println("\n您输入的字符不合法，请输入数字！！！");
            e.printStackTrace();
        }
    }

}


//定义全局变量：
//可以喝酒的总数
public int totalNums;
//剩下的空瓶数量
public int lastEmptyBottleNums;
//剩下的盖子数量
public int lastLidNums;
/**
 * 啤酒问题：啤酒2元一瓶，4个盖子可以换一瓶，2个空瓶（无盖子）可以换一瓶。
 */
//买酒（换酒）方法
private void buyBeer(int money){
    //1、拿钱买酒
    //整数相除不是四舍五入，而是直接舍去小数位，例如：int i = 3/2 = 1
    //3元可以买一瓶酒，剩1元。5元可以买两瓶酒，剩1元。
    int number = money / 2;
    //总喝酒数量累加
    totalNums += number;

    //2、空瓶子、盖子兑换成钱
    //算出当前剩余的全部盖子喝瓶子数，换算成金额继续购买
    int curEmptyBottleNums = lastEmptyBottleNums + number;
    int curLidNums = lastLidNums + number;
    //兑换的钱，保存在变量exchangeMoney中
    int exchangeMoney = 0;
    //2个空瓶（无盖子）可以换一瓶酒
    //整数相除不是四舍五入，而是直接舍去小数位，例如：int i = 3/2 = 1
    //3个空瓶 = 两个换1瓶酒 + 剩一个空瓶，3/2=1瓶酒
    //5个空瓶 = 两个换1瓶酒 + 两个换1瓶酒 + 剩一个空瓶，5/2=2瓶酒
    //一瓶酒相当于2元，故(curEmptyBottleNums/2)要乘2
    exchangeMoney += (curEmptyBottleNums/2)*2;
    //算出剩余的瓶子
    //% 模运算。示例：5 % 2 = 2 + 2 + 1 = 模运算结果为1；6 % 2 = 2 + 2 + 2 + 0 = 模运算结果为0
    //空瓶子有5个 = 2个换一瓶酒 + 2个换一瓶酒 + 剩1个空瓶，5 % 2 = 1，5个空瓶换了两瓶酒剩1个空瓶
    lastEmptyBottleNums = curEmptyBottleNums % 2;
    //同理，计算盖子
    exchangeMoney += (curLidNums/4)*2;
    lastLidNums = curLidNums % 4;

    //3、继续购买（兑换）酒
    if(exchangeMoney >= 2){//2元一瓶酒
        buyBeer(exchangeMoney);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

运行结果：

------------------------------- start - 1 ---------------------------------
啤酒问题：啤酒2元一瓶，4个盖子可以换一瓶，2个空瓶（无盖子）可以换一瓶。
请输入购买金额：2
2元可以喝到【1】瓶酒。
剩下的空瓶数量：1
剩下的盖子数量：1
------------------------------- end - 1 ---------------------------------



------------------------------- start - 2 ---------------------------------
啤酒问题：啤酒2元一瓶，4个盖子可以换一瓶，2个空瓶（无盖子）可以换一瓶。
请输入购买金额：5
5元可以喝到【3】瓶酒。
找回零钱：1元
剩下的空瓶数量：1
剩下的盖子数量：3
------------------------------- end - 2 ---------------------------------



------------------------------- start - 3 ---------------------------------
啤酒问题：啤酒2元一瓶，4个盖子可以换一瓶，2个空瓶（无盖子）可以换一瓶。
请输入购买金额：0
bye bye!

进程已结束,退出代码0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

文件搜索

搜索D:\aaa 目录中的.java 文件。

分析：

1. 目录搜索，无法判断多少级目录，所以使用递归，遍历所有目录。
2. 遍历目录时，获取的子文件，通过文件名称，判断是否符合条件。

代码实现：

public class DiGuiDemo3 {
    public static void main(String[] args) {
        // 创建File对象
        File dir  = new File("D:\\aaa");
      	// 调用打印目录方法
        printDir(dir);
    }

    public static void printDir(File dir) {
      	// 获取子文件和目录
        File[] files = dir.listFiles();
      	
      	// 循环打印
        for (File file : files) {
            if (file.isFile()) {
              	// 是文件，判断文件名并输出文件绝对路径
                if (file.getName().endsWith(".java")) {
                    System.out.println("文件名:" + file.getAbsolutePath());
                }
            } else {
                // 是目录，继续遍历,形成递归
                printDir(file);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

对“文件搜索”进行优化，将查找结果保存在map中返回、设置排除目录、记录查询时间、查找到文件（程序）后如何执行（启动），见这篇博客。

小结

• 递归是自己调用自己。
• 递归如果控制的不恰当，会形成递归的死循环，从而导致栈内存溢出错误！！
• 递归应该防止进入递归的死循环！

函数调用是有成本的，每一次调用都需要分配额外的栈空间用于存储参数、局部变量以及返回地址，需要进行额外的入栈和出栈操作。在递归调用的情况下，如果递归的次数比较多，这个成本是比较可观的，所以，如果程序可以比较容易地改为其他方式，应该考虑其他方式。

栈的空间不是无限的，一般正常调用都是没有问题的，但如果栈空间过深，系统就会抛出错误java.lang.StackOverflowError，即栈溢出。

学习自B站深入学习Java编程-黑马、《Java编程的逻辑》-马俊昌