递归,就是这么简单

1,087 阅读4分钟

递归

什么是递归?

维基百科给出了如下定义:

程序调用自身的编程技巧称为递归.递归作为一种算法在程序设计语言中广泛应用。

上面的说法略显官方。简而言之,递归就是自己调用自己,但是这个调用它是有一定条件的,比如:

  • 子问题须与原始问题为同样的事,且更为简单。
  • 调用自身的次数不能太多,否则会造成程序堆栈溢出。
  • 必须设置递归边界,也就是递归的结束条件,否则递归会无限循环直到程序堆栈溢出。

递归与循环的区别

  • 递归

优点:代码简洁、清晰(需要你理解算法,否则会更晕) 缺点:调用次数控制不好,容易造成堆栈溢出,此外,它的每次传递参数都是相当于在压栈,每次返回结果都相当于出栈,这个过程是非常影响执行效率的。

  • 循环

优点:逻辑简单,速度快 缺点:不能解决所有的问题,有些问题必须用递归实现。比如,著名的汉若塔问题,如果有谁可以用其他方式写出来我服。

递归的使用场景

关于使用场景,我总结了一句话:调用次数较少且用循环实现极为恶心的时候,可以尝试使用递归。

关于递归的几个实例

  1. 计算 int 形数组的总和
public class Main {

    private static int sum(int[] arr, int z) {

        if (z == arr.length) {
            return 0;
        }

        int x = sum(arr, z + 1);

        int res = arr[z] + x;

        return res;
    }


    public static void main(String[] args) {
        int arr[] = {1, 2};
        sum(arr, 0);
    }
}

这个示例最简单,当然这里是为了方便说明问题,实际上用循环实现才是最好的。目的就是计算 arr 数组各元素的总和,看输入参数,大家可以猜到返回结果是 3 。下面我说下看这类程序的小技巧。

首先,我们要找到程序的递归边界,也就是递归结束的条件(这样说也不准确,看具体的代码实现,有时递归边界确实是递归结束的条件,返回最终结果,但有时又是递归最后一层返回结果的条件,比如以下程序)。

  • 当 z = 2 时,这层递归返回 0 ,也就是 x = 0、返回到 z = 1 的这层递归。
  • 此时,res = arr[1] + 0 ,返回 res = 2 也就是 x = 2 给到 z = 0 的这层递归。
  • 这时,res = arr[0] + 2 = 3 至此,递归结束,返回结果给调用方。

没看懂的,请复制代码 debug 一步一步的运行。一开始看反正我是被绕晕的。

  1. 计算 1 到 100 的总和
public class Main {

    static int i = 1;

    public static void show(int sum) {
        sum = sum + i; //业务代码1
        //递归头
        if (i == 10) {
            System.out.println(sum);
            return;
        }
        i++;   //业务代码2
        show(sum); //递归体
    }

    public static void main(String[] args) {
        int sum = 0;
        show(sum);
    }
}

以上写法的递归边界,就属于我上面说的,它就是递归结束的条件。它的返回结果就是递归的最终结果,而不是上一层的结果。

  1. 斐波那契数列
public class Main {
 
    public static int f(int n) throws Exception {
        if(n==0){
           throw new Exception("参数错误!");
        }
        if (n == 1 || n == 2) {
            return 1;
        } else {
            return f(n-1)+f(n-2); //自己调用自己
        }
 }
 
 
    public static void main(String[] args) throws Exception {
        for (int i = 1; i <=10; i++) {
            System.out.print(f(i)+" ");
        }
    }  
}
  1. 计算文件夹大小

由于 File 类下length() (返回值类型为 long 型) 方法只能统计文件的大小,没有方法直接统计文件夹的大小,需要使用递归的方法遍历到所有的文件,并累加,最终计算出文件夹大小。

public class Main {

    public static void main(String[] args) {
        File dir = getDir();
        System.out.println(getFileLength(dir));
        System.out.println("统计完成!");
    }
    
    public static File getDir() {
        //1,创建键盘录入对象
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入一个文件夹路径:");
        //2,定义一个无限循环
        while(true) {
            //3,将键盘录入的结果存储并封装成File对象
            String line = sc.nextLine();
            File dir = new File(line);
            //4,对File对象判断
            if(!dir.exists()) {
                System.out.println("您录入的文件夹路径不存在,请重新录入:");
            }else if(dir.isFile()) {
                System.out.println("您录入的是文件路径,请重新录入:");
            }else {
                //5,将文件夹路径对象返回
                return dir;
            }
        }        
    }

    public static long getFileLength(File dir) {
        //1,定义一个求和变量
        long len = 0;
        //2,获取该文件夹下所有的文件和文件夹listFiles();
        File[] subFiles = dir.listFiles();
        //3,遍历数组
        if(subFiles != null) {
            for (File subFile : subFiles) {
                //4,判断是文件就计算大小并累加
                if(subFile.isFile()) {
                    len = len + subFile.length();
                    //5,判断是文件夹,递归调用
                }else {
                    len = len + getFileLength(subFile);
                }
            }
        }
        return len;
    }
}

总结:这篇主要是介绍下递归的定义、与循环的区别以及它的使用场景,最后提供了几个代码示例给大家研究,看不懂的请复制代码,debug 一步一步运行理解。

参考链接:www.jianshu.com/p/edfc4e35f…

推荐阅读:

1、java | 什么是动态代理

2、SpringBoot | 启动原理

3、SpringBoot | 自动配置原理

一个优秀的废人