Java基础之递归

1.1 概述

需求：扫描D:\test所有子文件夹及子子文件夹下的.jpg文件。

我们如果用循环来做这件事，我们不知道循环的结束条件，也不知道到底有多少层，所以比较麻烦。

我们可以用一种新的思想：递归。

递归举例：

​ 从前有一座山，山里有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：

​ 从前有一座山，山里有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：

​ 从前有一座山，山里有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：

。。。。。。。

故事如何才能结束：小和尚还俗了。庙塌了。山崩了。

Java中的递归：

​ 在方法的函数体中又调用了方法自己本身。

递归调用的细节：必须要求递归中有可以让函数调用的结束条件。否则函数一直调用，就会导致内存溢出。

1.2 递归累和

计算1 ~ 5的和

练习1：需求：计算1~5的和值，不许使用循环。

实现代码：

public class DiGuiDemo {
    public static void main(String[] args) {
        //计算1~5的和，使用递归完成
        int n = 5;
        // 调用求和的方法
        int sum = getSum(n);
        // 输出结果
        System.out.println(sum);
        
    }
    /*
      通过递归算法实现.
      参数列表:int
      返回值类型: int
    */
    public static int getSum(int n) {
        /*
           n为1时,方法返回1,
           相当于是方法的出口,n总有是1的情况
        */
        if(n == 1){
            return 1;
        }
        /*
          n不为1时,方法返回 n +(n-1)的累和
          递归调用getSum方法
        */
        return n + getSum(n-1);
    }
}

代码执行图解

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

1.3 递归求阶乘

练习2：需求：求5的阶乘！！

分析：

普及一下数学知识：

使用递归思想来完成

5! = 5 * 4!

     4! = 4 * 3!

        3! = 3 * 2!

           2! = 2 * 1!

              1! =1*0!

找规律：n! = n * (n-1)!

补充：0!等于1

结束条件：if(n <= 1) return 1;

递归方式：

代码如下所示：

步骤：

1）定义一个DiGuiDemo3测试类；

2）在这个类中的main函数中调用自定义函数jc2()，5作为函数的参数，使用一个变量result来接收返回的阶乘的值，并输出结果result；

3）自定义jc2()函数接收传递的参数5；

4）在自定义函数中书写if语句判断n是否小于等于1，如果小于等于1，则使用return返回1;

5）否则n>1时，使用return返回n * jc2(n - 1);

package cn.itcast.sh.digui.demo;
/*
* 方式2：使用递归思想来解决5的阶乘
*方式一： 5!=5*4*3*2*1;
*方式二：5!=5*4!
*            4!=4*3!
*                 3!=3*2!
*                        2!=2*1!
*                              1!=1*0!
*找规律：n!=n*(n-1)!
*找结束条件:
*  if(n<=1) return1;
*/
public class DiGuiDemo3 {
    public static void main(String[] args) {
        // 调用函数求5的阶乘
        int result=jc2(5);
        System.out.println(result);//120
    }
    //自定义函数求5的阶乘
    public static int jc2(int n) {
        // 结束条件
        if(n<=1)
        {
            return 1;
        }
        return n*jc2(n-1);
    }
}

上述代码内存图解如下所示：

1.4 递归注意事项

1）递归必须有结束条件，否则栈内存会溢出，称为死递归！栈炸了。

栈内存溢出报的异常如下所示：

2）递归次数不能太多，否则栈溢出。炸了

栈内存溢出报的异常如下所示：

总结：递归容器容易导致内存溢出。即使递归调用中有结束条件，但是如果递归的次数太多，也会发生内存溢出。

所以在开发中使用函数的递归调用时需谨慎。

1.5 递归打印所有子目录中的文件路径

需求：扫描D:\test所有子文件夹及子子文件夹下的.jpg文件，输出其绝对路径。

  分析：

   首先我们可以拿到D:\test下的所有儿子，我们判断儿子是不是文件夹，如果是，再次扫描儿子的文件夹，然后获取儿子下面的所有子文件和子文件夹，即就是D:\test的孙子，然后我们再判断孙子是不是文件夹等等，以此类推，最后我们输出其绝对路径；

  思路：

   A：封装父目录的File对象；

   B：获取父目录下的所有儿子的File数组；

   C：循环遍历，获取每个儿子；

   D：判断是否是文件夹

   是：回到步骤B 继续获取孙子

   否：判断是否是.jpg  结束递归的条件

   是：打印

   否：不管

   我们发现：B到D的过程是不断重复。我们可以封装成递归的函数。

步骤：

1）创建测试类FileTest1；

2）在FileTest1类的main函数中封装父目录D:\test的对象parent；

3）调用递归扫描的函数scanFolders(parent);

4）自定义函数scanFolders()，使用父目录对象parent调用listFiles()函数获得父目录下所有儿子的File数组files;

5）循环遍历，获取每个儿子对象file；

6）使用file对象调用isDirectory()函数判断是否是文件夹；

7）如果是文件夹，则递归调用scanFolders(file)函数;

8）如果不是文件夹，肯定是文件，使用file对象调用getName()函数获得文件的全名，调用endsWith()函数判断后缀名是否是.jpg,如果是输出文件所属的绝对路径；

package cn.itcast.sh.file.test;
import java.io.File;
/*
* 需求：扫描D:\\test所有子文件及子子文件下的.jpg文件，输出其绝对路径。
* 思路：
* A:创建父目录
* B:调用函数查找文件或者文件夹
* C:通过父目录对象调用函数获取所有儿子的File数组
* D:循环遍历所有的儿子,dir表示父目录D:\\test的每一个儿子
*      a:判断获取的儿子dir是否是文件夹 如果是 执行步骤B
*      b:不是，判断后缀名是否是.jpg,是，输出绝对路径
*
* 我们发现：B到D的过程是不断重复。我们可以封装成递归的函数。
*/
public class FileTest1 {
    public static void main(String[] args) {
        //封装父目录的对象
        File parent = new File("D:\\test");
        //调用函数查找文件或者文件夹
        scanFolderAndFile(parent);
    }
    //自定义函数扫描文件或者文件夹
    public static void scanFolderAndFile(File parent) {
        //通过父目录对象调用函数获取所有儿子的File数组
        File[] dirs = parent.listFiles();
        //循环遍历所有的儿子,dir表示父目录D:\\test的每一个儿子
        for (File dir : dirs) {
            /*
             * 判断获取的儿子dir是否是文件夹
             * 如果是文件夹，那么继续扫描或者查找儿子下面的所有文件或者文件夹
             * 以此类推
             * 如果不是文件夹，那么肯定是文件，判断后缀名是否是.jpg
             *      如果是.jpg 则输出其绝对路径
             */
            if(dir.isDirectory())
            {
                //说明是文件夹  继续找儿子下面的文件或者文件夹 执行扫描函数
                scanFolderAndFile(dir);
            }else
            {
                /*
                 * 说明不是文件夹，是文件,我们判断是否是.jpg
                 * dir.getName()表示获取文件的名字 mm.jpg
                 */
                if(dir.getName().endsWith(".jpg"))
                {
                    //说明文件的后缀名是.jpg 输出其绝对路径
                    System.out.println(dir.getAbsolutePath());
                }
            }
        }
    }
}

Java基础之递归

1.1 概述

需求：扫描D:\test所有子文件夹及子子文件夹下的.jpg文件。

我们如果用循环来做这件事，我们不知道循环的结束条件，也不知道到底有多少层，所以比较麻烦。

我们可以用一种新的思想：递归。

递归举例：

​ 从前有一座山，山里有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：

​ 从前有一座山，山里有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：

​ 从前有一座山，山里有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：

。。。。。。。

故事如何才能结束：小和尚还俗了。庙塌了。山崩了。

Java中的递归：

​ 在方法的函数体中又调用了方法自己本身。

递归调用的细节：必须要求递归中有可以让函数调用的结束条件。否则函数一直调用，就会导致内存溢出。

1.2 递归累和

计算1 ~ 5的和

练习1：需求：计算1~5的和值，不许使用循环。

实现代码：

public class DiGuiDemo {
    public static void main(String[] args) {
        //计算1~5的和，使用递归完成
        int n = 5;
        // 调用求和的方法
        int sum = getSum(n);
        // 输出结果
        System.out.println(sum);
        
    }
    /*
      通过递归算法实现.
      参数列表:int
      返回值类型: int
    */
    public static int getSum(int n) {
        /*
           n为1时,方法返回1,
           相当于是方法的出口,n总有是1的情况
        */
        if(n == 1){
            return 1;
        }
        /*
          n不为1时,方法返回 n +(n-1)的累和
          递归调用getSum方法
        */
        return n + getSum(n-1);
    }
}

代码执行图解

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

1.3 递归求阶乘

练习2：需求：求5的阶乘！！

分析：

普及一下数学知识：

使用递归思想来完成

5! = 5 * 4!

     4! = 4 * 3!

        3! = 3 * 2!

           2! = 2 * 1!

              1! =1*0!

找规律：n! = n * (n-1)!

补充：0!等于1

结束条件：if(n <= 1) return 1;

递归方式：

代码如下所示：

步骤：

1）定义一个DiGuiDemo3测试类；

2）在这个类中的main函数中调用自定义函数jc2()，5作为函数的参数，使用一个变量result来接收返回的阶乘的值，并输出结果result；

3）自定义jc2()函数接收传递的参数5；

4）在自定义函数中书写if语句判断n是否小于等于1，如果小于等于1，则使用return返回1;

5）否则n>1时，使用return返回n * jc2(n - 1);

package cn.itcast.sh.digui.demo;
/*
* 方式2：使用递归思想来解决5的阶乘
*方式一： 5!=5*4*3*2*1;
*方式二：5!=5*4!
*            4!=4*3!
*                 3!=3*2!
*                        2!=2*1!
*                              1!=1*0!
*找规律：n!=n*(n-1)!
*找结束条件:
*  if(n<=1) return1;
*/
public class DiGuiDemo3 {
    public static void main(String[] args) {
        // 调用函数求5的阶乘
        int result=jc2(5);
        System.out.println(result);//120
    }
    //自定义函数求5的阶乘
    public static int jc2(int n) {
        // 结束条件
        if(n<=1)
        {
            return 1;
        }
        return n*jc2(n-1);
    }
}

上述代码内存图解如下所示：

1.4 递归注意事项

1）递归必须有结束条件，否则栈内存会溢出，称为死递归！栈炸了。

栈内存溢出报的异常如下所示：

2）递归次数不能太多，否则栈溢出。炸了

栈内存溢出报的异常如下所示：

总结：递归容器容易导致内存溢出。即使递归调用中有结束条件，但是如果递归的次数太多，也会发生内存溢出。

所以在开发中使用函数的递归调用时需谨慎。

1.5 递归打印所有子目录中的文件路径

需求：扫描D:\test所有子文件夹及子子文件夹下的.jpg文件，输出其绝对路径。

  分析：

   首先我们可以拿到D:\test下的所有儿子，我们判断儿子是不是文件夹，如果是，再次扫描儿子的文件夹，然后获取儿子下面的所有子文件和子文件夹，即就是D:\test的孙子，然后我们再判断孙子是不是文件夹等等，以此类推，最后我们输出其绝对路径；

  思路：

   A：封装父目录的File对象；

   B：获取父目录下的所有儿子的File数组；

   C：循环遍历，获取每个儿子；

   D：判断是否是文件夹

   是：回到步骤B 继续获取孙子

   否：判断是否是.jpg  结束递归的条件

   是：打印

   否：不管

   我们发现：B到D的过程是不断重复。我们可以封装成递归的函数。

步骤：

1）创建测试类FileTest1；

2）在FileTest1类的main函数中封装父目录D:\test的对象parent；

3）调用递归扫描的函数scanFolders(parent);

4）自定义函数scanFolders()，使用父目录对象parent调用listFiles()函数获得父目录下所有儿子的File数组files;

5）循环遍历，获取每个儿子对象file；

6）使用file对象调用isDirectory()函数判断是否是文件夹；

7）如果是文件夹，则递归调用scanFolders(file)函数;

8）如果不是文件夹，肯定是文件，使用file对象调用getName()函数获得文件的全名，调用endsWith()函数判断后缀名是否是.jpg,如果是输出文件所属的绝对路径；

package cn.itcast.sh.file.test;
import java.io.File;
/*
* 需求：扫描D:\\test所有子文件及子子文件下的.jpg文件，输出其绝对路径。
* 思路：
* A:创建父目录
* B:调用函数查找文件或者文件夹
* C:通过父目录对象调用函数获取所有儿子的File数组
* D:循环遍历所有的儿子,dir表示父目录D:\\test的每一个儿子
*      a:判断获取的儿子dir是否是文件夹 如果是 执行步骤B
*      b:不是，判断后缀名是否是.jpg,是，输出绝对路径
*
* 我们发现：B到D的过程是不断重复。我们可以封装成递归的函数。
*/
public class FileTest1 {
    public static void main(String[] args) {
        //封装父目录的对象
        File parent = new File("D:\\test");
        //调用函数查找文件或者文件夹
        scanFolderAndFile(parent);
    }
    //自定义函数扫描文件或者文件夹
    public static void scanFolderAndFile(File parent) {
        //通过父目录对象调用函数获取所有儿子的File数组
        File[] dirs = parent.listFiles();
        //循环遍历所有的儿子,dir表示父目录D:\\test的每一个儿子
        for (File dir : dirs) {
            /*
             * 判断获取的儿子dir是否是文件夹
             * 如果是文件夹，那么继续扫描或者查找儿子下面的所有文件或者文件夹
             * 以此类推
             * 如果不是文件夹，那么肯定是文件，判断后缀名是否是.jpg
             *      如果是.jpg 则输出其绝对路径
             */
            if(dir.isDirectory())
            {
                //说明是文件夹  继续找儿子下面的文件或者文件夹 执行扫描函数
                scanFolderAndFile(dir);
            }else
            {
                /*
                 * 说明不是文件夹，是文件,我们判断是否是.jpg
                 * dir.getName()表示获取文件的名字 mm.jpg
                 */
                if(dir.getName().endsWith(".jpg"))
                {
                    //说明文件的后缀名是.jpg 输出其绝对路径
                    System.out.println(dir.getAbsolutePath());
                }
            }
        }
    }
}