方法递归

递归的形式和特点

什么是方法递归

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

递归的形式

直接调用：方法自己调用自己
间接调用：方法调用其他方法，其他方法又返回调用自己

package com.shouyeren.algorithm.recursion;

/**
 * 递归的形式
 */
public class recursionDemo1 {
    public static void main(String[] args) {
        test();
        test1();
    }

    public static void test(){
        System.out.println("test方法被执行了");
        test();//方法递归 直接递归形式
    }

    public static void test1(){
        System.out.println("test方法被执行了");
        test2();//方法递归 间接递归形式
    }

    public static void test2(){
        System.out.println("test方法被执行了");
        test1();
    }
}

递归的方法无限调用自己，无法终止，会出现StackOverflowError 堆栈溢出错误

递归的算法流程、核心要素

案例

需求：计算1—n的阶乘的结果，使用递归思想解决，从数学思维上理解递归的流程和核心点

package com.shouyeren.algorithm.recursion;

/**
 * 递归的算法和执行流程
 */
public class recursionDemo2 {
    public static void main(String[] args) {
        System.out.println(test(5));//120
    }

   public static int test(int n){
        if (n == 1){
            return 1;
        }else {
            return test(n - 1) * n;
        }
   }
}

递归解决问题的思路

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

递归算法的三要素大体可以总结为：

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

递归的终结点：f(1)

递归的方向必须走向终结点

经典案例

猴子吃桃:

猴子第一天摘下若干桃子，当即吃了一半，觉得好吃不过瘾，于是又多吃了一个，之后每天如此，等到第十天的时候发现只有一个桃子了。

请问第一天猴子摘下了多少个桃子？

package com.shouyeren.algorithm.recursion;

/**
 * 猴子吃桃问题
 */
public class recursionDemo4 {
    public static void main(String[] args) {
        System.out.println(test(1));//1534
    }


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

非规律化递归案例

文件搜索

package com.shouyeren.algorithm.recursion;

import java.io.File;

/**
 * 文件搜索递归实现
 */
public class recursionDemo5 {
    public static void main(String[] args) {
        searchFile(new File("D:/"),"更新日志.txt");
    }


    /**
     * 搜索某个目录下的全部文件，找到我们想要的文件
     * @param dir 被搜索的源目录
     * @param fileName 被搜索的文件名
     */
   public static void searchFile(File dir,String fileName){
       if (dir != null && dir.isDirectory()){
           //提取当前文件夹下的一级对象

            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);
                    }
                }
            }
       }else {
           System.out.println("对不起，您当前搜索的位置不是文件夹或您要搜索的文件夹不存在！");
       }

   }
}

啤酒问题

需求：

啤酒2元一瓶，四个盖子可以换一瓶，两个空瓶可以换一瓶，请问10元钱可以喝多少瓶啤酒，剩余多少个空瓶和盖子？

package com.shouyeren.algorithm.recursion;

/**
 * 需求：
 * 啤酒2元一瓶，四个盖子可以换一瓶，两个空瓶可以换一瓶，
 * 请问10元钱可以喝多少瓶啤酒，剩余多少个空瓶和盖子？
 */
public class recursionDemo6 {
    //定义一个静态成员变量用于储存可以买的酒的数量
    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("剩余的瓶子数：" + lastBottleNumber);
        System.out.println("剩余的盖子数：" + lastCoverNumber);
    }

    public static void buy(int money){
        //2.统计当前能买多少瓶酒
        int buyNumber = money / 2;
        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);
        }
    }
}