方法递归详解

什么是方法递归

方法直接调用自己或者间接调用自己的形式称为方法递归（ recursion）。 递归做为一种算法在程序设计语言中广泛应用。

递归的形式

直接递归：方法自己调用自己。

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

方法递归存在的问题？

递归如果没有控制好终止，会出现递归死循环，导致栈内存溢出现象。

案例

/**
         递归的形式
 */
public class RecursionDemo01 {
    public static void main(String[] args) {
        test2();
    }
 
    public static void test(){
        System.out.println("=======test被执行========");
        test(); // 方法递归 直接递归形式
    }
 
    public static void test2(){
        System.out.println("=======test2被执行========");
        test3(); // 方法递归 间接递归
    }
 
    private static void test3() {
        System.out.println("=======test3被执行========");
        test2();
    }
}

执行结果： 

递归案例导学-计算1-n的阶乘

需求：

计算1-n的阶乘的结果，使用递归思想解决，我们先从数学思维上理解递归的流程和核心点。

分析：

假如我们认为存在一个公式是 f(n) = 1*2*3*4*5*6*7*…(n-1)*n;

那么公式等价形式就是： f(n) = f(n-1) *n。

如果求的是 1-5的阶乘的结果，应用上述公式手工计算如下：

先往下走

f(5) =  f(4) * 5

f(4) =  f(3) * 4

f(3) =  f(2) * 3

f(2) =  f(1) * 2

f(1) =  1

然后再往回走，就能计算出结果。

代码：

/**
      目标：递归的算法和执行流程
 */
public class RecursionDemo02 {
    public static void main(String[] args) {
        int result = f(5);
        System.out.println("5的阶乘是："+result);
    }
 
    public static int f(int n){
        if(n == 1){
            return 1;
        }else {
            return f(n - 1) * n;
        }
    }
}

执行流程

随着程序的执行，方法依次入栈，如下：

然后从上往下方法依次被执行完，那么依次被弹栈。

递归解决问题的思路

把一个复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。

递归算法三要素

递归的公式： f(n) =  f(n-1) * n;

递归的终结点：f(1)

递归中的递推方向必须走向终结点。

递归算法

分析问题时能分析出每一步或者每一大步都是在做同样的事情，方可用递归算法。假设方法f(n)能解决复杂问题，再把方法f(n)化为更小规模问题解决方法f(n+1)或者f(n-1)，再把前面的方法化为更更小的问题解决方法，直到最小问题的解决。

递归的经典问题

猴子第一天摘下若干桃子，当即吃了一半，觉得好不过瘾，于是又多吃了一个。 第二天又吃了前天剩余桃子数量的一半，觉得好不过瘾，于是又多吃了一个。 以后每天都是吃前天剩余桃子数量的一半，觉得好不过瘾，又多吃了一个。 等到第10天的时候发现桃子只有1个了。

需求：请问猴子第一天摘了多少个桃子？

分析： 整体来看，每一天都是做同一个事件，典型的规律化问题，考虑递归三要素：

        递归公式：

              f(x) - f(x)/2 - 1 = f(x+1)
              2f(x) - f(x) - 2 = 2f(x + 1)
              f(x) = 2f(x + 1) + 2

        递归终结点：f（10） = 1。

        递归方向：为了求f(1)逐渐递推到f(10),所以是走向终结点。

代码:

public class RecursionDemo04 {
    public static void main(String[] args) {
        System.out.println(f(1));
        System.out.println(f(2));
        System.out.println(f(3));
    }
 
    public static int f(int n){
        if(n == 10){
            return 1;
        }else {
            return 2 * f(n + 1) + 2;
        }
    }
}

非规律化递归问题解决方法

非规律化递归问题自己看着办，需要流程化的编程思维，即模拟用户解决问题的过程。

非规律化递归案例-文件搜索

需求：从D:盘中，搜索出某个文件名称并输出绝对路径。

分析：

        先得到目标文件夹（D:\）下的一级文件对象

        遍历全部一级文件对象，判断是否是文件

        如果是文件，判断是否是自己想要的

        如果是文件夹，重复上述过程

代码：

/**
    目标：去D判断搜索 eDiary.exe文件
 */
public class RecursionDemo05 {
    public static void main(String[] args) {
        // 2、传入目录 和  文件名称
        searchFile(new File("D:/") , "eDiary.exe");
    }
 
    /**
     * 1、搜索某个目录下的全部文件，找到我们想要的文件。
     * @param dir  被搜索的源目录
     * @param fileName 被搜索的文件名称
     */
    public static void searchFile(File dir,String fileName){
        // 3、判断dir是否是目录
        if(dir != null && dir.isDirectory()){
            // 可以找了
            // 4、提取当前目录下的一级文件对象
            File[] files = dir.listFiles(); // null  []
            // 5、判断是否存在一级文件对象，存在才可以遍历
            if(files != null && files.length > 0) {
                for (File file : files) {
                    // 6、判断当前遍历的一级文件对象是文件 还是 目录
                    if(file.isFile()){
                        // 7、是不是咱们要找的，是把其路径输出即可
                        if(file.getName().contains(fileName)){
                            System.out.println("找到了：" + file.getAbsolutePath());
                            // 启动它。
                            try {
                                Runtime r = Runtime.getRuntime();
                                r.exec(file.getAbsolutePath());
                            } catch (IOException e) {
                                e.printStackTrace();
                            }
                        }
                    }else {
                        // 8、是文件夹，需要继续递归寻找
                        searchFile(file, fileName);
                    }
                }
            }
        }else {
            System.out.println("对不起，当前搜索的位置不是文件夹！");
        }
    }
}

非规律化递归案例-啤酒问题

需求：啤酒2元1瓶，4个盖子可以换一瓶，2个空瓶可以换一瓶， 请问10元钱可以喝多少瓶酒，剩余多少空瓶和盖子。

答案：15瓶 3盖子 1瓶子。

/**
    目标：啤酒2元1瓶，4个盖子可以换一瓶，2个空瓶可以换一瓶，
        请问10元钱可以喝多少瓶酒，剩余多少空瓶和盖子。
        答案：15瓶 3盖子 1瓶子
 */
public class RecursionDemo06 {
 
    // 定义一个静态的成员变量用于存储可以买的酒数量
    public static int totalNumber; // 总数量
    public static int lastBottleNumber; // 记录每次剩余的瓶子个数
    public static int lastCoverNumber; // 记录每次剩余的盖子个数
 
 
    public static void main(String[] args) {
        // 1、拿钱买酒
        buy(10);
        System.out.println("总数：" + totalNumber);
        System.out.println("剩余盖子数：" + lastCoverNumber);
        System.out.println("剩余瓶子数：" + lastBottleNumber);
    }
 
    public static void buy(int money){
        // 2、看可以立马买多少瓶
        int buyNumber = money / 2; // 5
        totalNumber += buyNumber;
 
        // 3、把盖子 和瓶子换算成钱
        // 统计本轮总的盖子数  和 瓶子数
        int coverNumber = lastCoverNumber + buyNumber;
        int bottleNumber = lastBottleNumber + buyNumber;
 
        // 统计可以换算的钱
        int allMoney = 0;
        if(coverNumber >= 4){
            allMoney += (coverNumber / 4) * 2;
        }
        lastCoverNumber = coverNumber % 4;
 
        if(bottleNumber >= 2){
            allMoney += (bottleNumber / 2) * 2;
        }
        lastBottleNumber = bottleNumber % 2;
 
        if(allMoney >= 2){
            buy(allMoney);
        }
    }
}