递归，就是这么简单

拼搏现实的明天。 2021-11-11 12:42 357阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3R1cm9kb2c_size_16_color_FFFFFF_t_70]

#### 什么是递归？ ####

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

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

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

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

#### 递归与循环的区别 ####

*  递归

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

*  循环

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

#### 递归的使用场景 ####

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

#### 关于递归的几个实例 ####

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 一步一步运行理解。

参考链接：[https://www.jianshu.com/p/edfc4e35f383][https_www.jianshu.com_p_edfc4e35f383]

**推荐阅读：**

[1、java | 什么是动态代理][1_java _]

[2、SpringBoot | 启动原理][2_SpringBoot _]

[3、SpringBoot | 自动配置原理][3_SpringBoot _]

![一个优秀的废人][aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8zMjgyMTM0LTU1NTk1NDFkMWM4Y2ZiNmQ]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3R1cm9kb2c_size_16_color_FFFFFF_t_70]: /images/20211109/35dc24574efa46ccb42fd3153c345b79.png
[https_www.jianshu.com_p_edfc4e35f383]: https://www.jianshu.com/p/edfc4e35f383
[1_java _]: http://mp.weixin.qq.com/s?__biz=MzU2MDY0NDA1MQ==&mid=2247483991&idx=1&sn=9e975618909b78006aaa9a3f001959f1&chksm=fc05a8ebcb7221fd4d9e7e8b645a5b1bd2536bc49a3eaf34eb18c1f7bcc33337ecd98af54e98&scene=21#wechat_redirect
[2_SpringBoot _]: http://mp.weixin.qq.com/s?__biz=MzU2MDY0NDA1MQ==&mid=2247484325&idx=1&sn=ef09f84b1597285896adad51a019e33d&chksm=fc05a919cb72200f0c6bcd3ce0832e3b7954d79b7529e07c133c394de9e9153813acd623fbcc&scene=21#wechat_redirect
[3_SpringBoot _]: http://mp.weixin.qq.com/s?__biz=MzU2MDY0NDA1MQ==&mid=2247483960&idx=1&sn=0f84bbb92c5cb5298388056bef405aff&chksm=fc05a884cb722192e33ea62ad1febdc79e2a101d4ca2e8171760c1dda14cab940320209a088a&scene=21#wechat_redirect
[aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8zMjgyMTM0LTU1NTk1NDFkMWM4Y2ZiNmQ]: /images/20211109/b2cb9206cde5453cb8e27b9f2dad1368.png