认识递归的形式

• 递归是一种算法，在程序设计语言中广泛应用。
• 从形式上来说：方法调用自身的形式称为方法递归（recursion）。

递归的形式

• 直接递归：方法自己调用自己
• 间接递归：方法调用其他方法，其他方法又回调方法自己

使用方法递归时需要注意的问题：

• 递归如果没有控制好终止，会出现递归死循环，导致栈内存溢出错误(StackOverflowError)

应用、执行流程、算法思想

案例导学-计算n的阶乘

需求：

        计算n的阶乘，5的阶乘=1*2*3*4*5；6的阶乘=1*2*3*4*5*6；

public class Test {
    public static void main(String[] args) {
        System.out.println("5的阶乘是：" + f(5));
    }

    private static int f(int n) {
        if (n == 1){
            return 1;
        }else {
            return f(n - 1) * n;
        }
    }
}

递归算法三要素：

• 递归的公式：f（n ）= f（n-1）*n；
• 递归的终结点：f（1）；
• 递归的方向必须走向终结点。

案例：猴子吃桃问题

public class Test {
    public static void main(String[] args) {
        System.out.println("猴子第一天摘的桃子数为：" + f(1));
    }

    public static int f(int n){
        if (n == 10){
            return 1;
        }else {
            return 2 * (f(n + 1) +1);
        }
    }
}

其他应用：文件搜索

案例：

需求：从D:盘中，搜索“QQ.exe”这个文件，找到后直接输出其位置。

分析：

1. 先找出D:盘下所有一级文件对象
2. 遍历全部一级文件对象，判断是否是文件
3. 如果是文件，判断是否是自己想要的
4. 如果是文件夹，需要继续进入到该文件夹，重复上述操作

import java.io.File;

public class Test {
    public static void main(String[] args) {
       searchFile(new File("D:/"),"QQ.exe");
    }

    /**
     * 去目录下搜寻某个文件
     * @param dir 目录
     * @param fileName 要搜索的文件名称
     */
    private static void searchFile(File dir, String fileName) {
        // 把非法的情况都拦截住
        if (dir == null || !dir.exists() || dir.isFile()){
            return; // 代表无法搜索
        }

        // dir不是null，且存在，一定是目录
        // 获取当前目录下的全部一级文件对象
        File[] files = dir.listFiles();

        // 判断当前目录下是否存在一级文件对象，以及是否可以拿到一级文件对象
        if (files != null && files.length > 0){
            // 遍历全部一级文件
            for (File file : files) {
                // 判断文件是否是文件，还是文件夹
                if (file.isFile()){
                    // 是文件，判断这个文件是否是我们要找的
                    if (file.getName().contains(fileName)){
                    System.out.println("找到了：" + file.getAbsolutePath());
                    }
                }else {
                    // 是文件夹，继续重复这个过程（递归）
                    searchFile(file,fileName);
                }
            }
        }
    }
}

练习：删除非空文件夹

import java.io.File;

public class Test {
    public static void main(String[] args) {
       // 目标：删除非空文件夹，独立功能独立非法
        File dir = new File("D:\\resource\\文档");
        deleteDir(dir);
    }

    private static void deleteDir(File dir) {
        if (dir == null || !dir.exists()){
            return;
        }
        if (dir.isFile()){
            dir.delete();
            return;
        }

        // dir存在且是文件夹，获取里面的一级文件对象
        File[] files = dir.listFiles();
        if (files == null){
            return;
        }
        // 这是一个有内容的文件夹，干掉里面的内容，再干掉自己
        for (File file : files) {
            if (file.isFile()){
                file.delete();
            }else {
                deleteDir(file);
            }
        }
        dir.delete();
    }
}

案例：啤酒问题，啤酒2元一瓶，4个盖子可以换一瓶，2个瓶子可以换一瓶，请问10元能换多少瓶酒

public class Test {
    public static int totalNumber; //总酒数
    public static int lastBottleNumber; //剩余酒瓶数
    public static int lastCoverNumber; //剩余瓶盖数
    public static void main(String[] args) {
        buy(10);

        System.out.println("总共可以喝的瓶数为：" + totalNumber);
        System.out.println("剩余酒瓶数：" + lastBottleNumber);
        System.out.println("剩余瓶盖数：" + lastCoverNumber);
    }

    private static void buy(int money) {
        int buyNumber = money / 2;
        money = money % 2;
        totalNumber += buyNumber;

        int allBottleNumber = lastBottleNumber + buyNumber;
        int allCoverNumber = lastCoverNumber + buyNumber;

        int allMoney = 0;

        if (allBottleNumber >= 2){
            allMoney += (allBottleNumber / 2) * 2;
        }
        lastBottleNumber = allBottleNumber % 2;

        if (allCoverNumber >= 4){
            allMoney += (allCoverNumber / 4) * 2;
        }
        lastCoverNumber = allCoverNumber % 4;

        allMoney += money;
        if (allMoney >= 2){
            buy(allMoney);
        }
    }
}