递归：先递进，再回归

您好，我是湘王，这是我的51CTO博客，欢迎您来，欢迎您再来～

虽然高端的知识要用最朴素有趣的方式来表达才更容易让人接受，但有些专业的内容却不能有半点马虎，必须严肃对待。后续的内容会在谈笑中慢慢向严谨转变，在轻松中缓缓传递认真的态度，也会在日复一日的坚持中不知不觉完成积累。

言归正传，之前在《编程逻辑》中提到过，常见的编程逻辑，也就是控制流有三种，分别是顺序、分支和循环。在那也留了一个小悬念：这哥仨其实还有两个小兄弟没露面。因为这俩出镜不多，所以见过的人不多，但他俩的名字，可能很多人都知道。一个叫「递归」，一个叫「回调」。

和前面仨不同，他们俩在逻辑上比较绕，属于烧脑的那种。

先从「递归」说起。

网上很多文章都讲过「递归」——对，出现最多就是斐波那契数列，公式是：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 2，n ∈ N*)。或者用更直白的话来表达，就是：「先递进，再回归」。可以参看下面的图来理解：

这么看的话，就一目了然了。

如果用代码来表示，就是：

// 递归计算斐波那契数列
public static int calc(int n) {
  // 特殊情况，分开讨论
  if (n == 1 || n == 2) {
    return 1;
  }
  if (n > 2) {
    // 递归调用
    return calc(n - 1) + calc(n - 2);
  }

  // 如果输入错误的n，一律返回-1
  return -1;
}

如果只是计算数学公式，那递归就简单得有点无聊了。

递归真正经典的应用在于读取计算机文件目录。下面是示例代码：

/**
 * 以递归方式列出所有文件
 * 
 * @param dir
 * @param spance
 */
public static void listFile(File dir, String spance) {
  // 列出所有的子文件
  File[] files = dir.listFiles();
  for (File file : files) {
    // 如果是文件，则输出文件名字
    if (file.isFile()) {
      System.out.println(spance + file.getName());
      // 如果是文件夹，则输出文件夹的名字，并递归遍历该文件夹
    } else if (file.isDirectory()) {
      System.out.println(spance + file.getName());
      // 递归遍历
      listFile(file, "|--" + spance);
    }
  }
}

其实递归的作用挺大的，只是平常编程中用的不多而已。除了遍历显示目录，还有两个最常用的场景，就是在电商网站中，地区多级联动和展示角色所拥有的菜单，就像下面展示的那样。

地区级联菜单（以XXXX号为例）：

角色拥有菜单（以XXXX为例）：

可以看到并掌握的规律是：只要是有这种层级关系的，都可以用递归来实现。

至于怎么实现，可以留给感兴趣的童鞋自己玩玩。不过给点小提示是：递归的数据结构一定要设计好，不然没法实现。

（关于数据结构该如何设计，以及数据库表该如何设计，这个后面都会讲到的）

感谢您的大驾光临！咨询技术、产品、运营和管理相关问题，请关注后留言。欢迎骚扰，不胜荣幸～