递归

递归 一种通过调用某个方法来描述需要重复进行的操作。该方法的特点就是可以自己调用自己。

案例一

  1. 排队的问题

    在生活中,我们经常需要排队。排队时,我们怎么才能知道自己所排在第几位呢?

    我们也许会想到数自己前面有几个人,这就是典型的迭代思想。就像是一个 while 循环,只要前面还有没数过的人,就不会停止。这种方式相对来说是比较直观的,但是同样也有局限性。比如在排队时,遇到了转弯,我们看不到前面的人怎么办呢?

    有一个方法,我们可以通过询问前面一个人他所处的位置。假设有 A、B、C、D 四个人,D 询问 C 所在的位置,C 询问 B 所在位置,B 询问 A 所在的位置。A 知道自己排在第一位(他不需要再问别人了,这一个询问的过程结束),然后告诉 B,那 B 就知道自己在第二位;然后 B 告诉 C,C 也就知道了自己在第三位;最后 C 告诉 D 他在第三位时,D 也就知道自己所在的位置了。这就是使用递归思想来分析问题——每个人都来回答一个问题,从而使这个问题多次 重现(recur)。

    这一点也是递归思想的精髓所在,递归方法涉及多个进行合作的单元,每个单元负责解决问题的一小部分。例如刚刚那个例子,每个人都向前询问一个问题,最后每个人又向后回答一个问题,而不是由一个人来负责统计所有的人数。

  2. 迭代到递归的转变

    根据传递的长度 length,打印出 length 个“ * ”

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    /**
    * 迭代
    *
    * @param length
    */
    public void writeStars1(int length) {
    for (int i = 0; i < length; i++) {
    System.out.print("*");
    }
    System.out.println();
    }

    /**
    * 递归
    *
    * @param length
    */
    public void writeStars2(int length) {
    if (length == 0) {
    System.out.println();
    } else {
    System.out.print("*");
    writeStars2(length - 1);
    }
    }

    上面这两个方法最终结果都是一样的。不同的是,迭代好比是一个人来统计所有的人数。递归则是由每个人回答同一个问题,由于每个人所在的位置不同,所回答的结果也不相同。

递归方法的结构

1
2
3
4
public void writeStars3(int length) {
System.out.println("*");
writeStars3(length - 1);
}

我们看一下上面这段代码,如果执行这段代码,程序并不会停止,会一直在自己调用自己执行下去。这也就是我们可能会遇到的 无穷递归(infinite recursion)。

递归方法有两个重要的组成部分:一个 基本情况 (base case)和一个 递归情况(recursive case)。

基本情况 一种简单到不需要递归调用就可以解决的情况。

递归情况 一种需要把整个问题转化成一个相同种类的,比较简单的,而且可以通过递归调用来解决的问题的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* 通过注释来解释基本情况和递归情况
*
* @param length
*/
public void writeStars2(int length) {
if (length == 0) {
// 基本情况
System.out.println();
} else {
// 递归情况
System.out.print("*");
writeStars2(length - 1);
}
}

案例二

我们有一个 LinkedList 集合,现在需要按照倒叙把集合的内容打印出来,打印完之后集合里面不要有数据。

  1. 通过迭代实现

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    LinkedList<String> list = new LinkedList<>();
    list.add("a");
    list.add("b");
    list.add("c");
    list.add("d");
    list.add("e");
    list.add("f");

    System.out.println(list);

    for (int i = list.size() - 1; i >= 0; i--) {
    System.out.print(list.get(i) + " ");
    }
    list.clear();
    System.out.println();
    System.out.println(list);

    输出结果

    1
    2
    3
    [a, b, c, d, e, f]
    f e d c b a
    []

    看到上面的结果,显然是符合要求的。那我们如果使用递归,该怎么实现呢?

  2. 通过递归实现

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    public static void main(String[] args) {

    LinkedList<String> list = new LinkedList<>();
    list.add("a");
    list.add("b");
    list.add("c");
    list.add("d");
    list.add("e");
    list.add("f");

    System.out.println(list);

    Iterator<String> iterator = list.iterator();
    writeArray(iterator);

    System.out.println();
    System.out.println(list);
    }

    /**
    * 递归实现
    * @param iterator
    */
    private static void writeArray(Iterator<String> iterator) {
    // 如果迭代器中还有数据,才进行递归计算
    if (iterator.hasNext()) {
    // 获得当前指针的参数
    String next = iterator.next();
    // 删除当前指针
    iterator.remove();
    // 使用递归计算
    writeArray(iterator);
    System.out.print(next + " ");
    }
    }

    输出结果

    1
    2
    3
    [a, b, c, d, e, f]
    f e d c b a
    []

由上述代码可以看出,使用递归算法,也可以同样得到结果,并且可以不使用 for 循环来完成任务。

调用栈

调用栈 用来跟踪所调用方法的顺序的内部结构。

了解递归的底层机制,对于初学者来说是很有帮助的。我们先来分析下面这段代码:

1
2
3
4
5
6
7
8
9
10
11
12
public static void main(String[] args) {
draw();
draws();
}

private static void draw(){
System.out.println(" 在纸上画了一幅画 ");
}
private static void draws(){
draw();
draw();
}

我们来人工 debug 一下这段代码。

  1. 程序首先进入 main 方法;
  2. 然后程序会停止执行 main 方法,转而去执行 draw 方法,当程序执行完 draw 方法时,会回到 main 方法当中;
  3. 接着需要执行 draws 方法,draws 方法又会去调用两次 draw 方法。而此时位于顶端的方法则是我们正在执行的方法 draw;
  4. 当我们执行 draw 时,回到了 draws 上面,执行完 draws 后,最终会回到 main 方法中;

调用一个方法我们就把它放在最上面的位置,这就是 Java 的 调用栈(call stack)

了解了什么是调用栈,则可以利用调用栈来分析刚刚那个递归倒叙是如何工作的了。

案例三

整数的密运算 。Math.pow(x, y) 可以进行 x 的 y 次幂 运算。但是如果要通过递归该如何实现呢?

为求简单,我们只考虑整数的情况。也就是说我们不考虑负指数,因为它的结果不是整数。

在递归情况中,我们已知 y > 0。我们至少需要再乘一个 x:x 的 y 次幂=x * x 的 y-1 次幂$x^y = x * x^z$)。由此我们可通过以下代码实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) {
System.out.println(Math.pow(3, 5));
System.out.println(pow(3, 5));
}

private static int pow(int x, int y) {
// 按照定义,任何整数的零次幂都是 1
if (y == 0) {
return 1;
} else {
return x * pow(x, y - 1);
}
}

运算结果

1
2
243.0
243

案例四

我们在写程序时,通常都会使用包含上下级结构的码表,例如下面这个数据:

1
2
3
4
5
6
7
8
SysCode{scId='01', itemName=' 测试 1', sort=1, fScId='null', cDesc=' 测试测试 1'}
SysCode{scId='02', itemName=' 测试 2', sort=1, fScId='01', cDesc=' 测试测试 2'}
SysCode{scId='03', itemName=' 测试 3', sort=3, fScId='01', cDesc=' 测试测试 3'}
SysCode{scId='04', itemName=' 测试 4', sort=2, fScId='01', cDesc=' 测试测试 4'}
SysCode{scId='05', itemName=' 测试 5', sort=1, fScId='03', cDesc=' 测试测试 5'}
SysCode{scId='06', itemName=' 测试 6', sort=2, fScId='03', cDesc=' 测试测试 6'}
SysCode{scId='07', itemName=' 测试 7', sort=2, fScId='null', cDesc=' 测试测试 2'}
SysCode{scId='08', itemName=' 测试 8', sort=1, fScId='07', cDesc=' 测试测试 2'}

分析以上代码,我们可以根据 fScId 封装上下级
关系,首先在 SysCode 类中增加一个 children 集合来保存子集。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* 使用递归创建子集
*
* @param scId
* @param list
* @return
*/
private List<SysCode> getSysCodeChildren(String scId, List<SysCode> list) {
List<SysCode> sysCodeList = new ArrayList<>();
list.forEach(e -> {
if (null != e.getfScId() && e.getfScId().equals(scId)) {
e.setChildren(getSysCodeChildren(e.getScId(), list));
sysCodeList.add(e);
}
});
return sysCodeList;
}

递归回溯

很多问题都可以通过系统地检查各种可能性来求解。比如,一个迷宫得游戏,要从入口找到出口,可以检查每一条线路,直到找到可行的线路。

很多使用穷举搜索求解得问题都能够用回溯法(backtracking)求解。回溯法是一种适宜用递归方式表示的问题求解方法。因此,这种方法也称为 递归回溯(recursive backtracking)。

(递归)回溯法 一种搜索问题解的通用算法,它先找出可能得候选解,一旦确定某个候选解不适合,就立刻放弃进一步尝试(回溯)。

案例分析

移动线路问题

考虑一个标准的平面直角坐标系(x, y),假设从原点(0, 0)出发,可以进行以下三种移动方式:
线路移动说明

  • 向北移动(用“ N ”表示),每次移动纵坐标 +1;
  • 向东移动(用“ E ”表示),每次移动横坐标 +1;
  • 向东北移动(用“ NE ”表示),每次纵坐标,横坐标各 +1;

如上图所示,从原点出发,会有三种不同的移动方式。现在定义一种移动路线问题:通过一系列移动,从原点到坐标(x, y)。例如,通过移动序列:N -> NE -> N 可以到达(1, 3)。

每个适用于回溯法解决的问题都具有包含问题所有可能解的解空间(solution space)。可以把解空间想象成一颗决策树(decision tree)。对于我们要解决的移动线路问题来说,每次移动方案都是选择的结果。

决策树

考虑从原点(0, 0)到(1, 2),所有可能的移动序号是:

  • N -> N -> E
  • N -> E -> N
  • N -> NE
  • E -> N -> N
  • NE -> N

用程序该如何找出这些解呢?对于大多数回溯问题,最终都会编写两个方法。一般会定义一个含有反应问题特性的参数的公有方法。另外会定义一个包含一些额外参数,执行实际回溯处理过程的私有方法。

因为要使用递归,所以需要确定基本情况和递归情况这两个部分。回溯法通常包含两种不通的基本情况。找到解时,停止回溯,这也是递归过程的一个基本情况。发现遇到死路的时候,停止继续搜索。

在回溯搜索过程中,如果既没有找到问题的解,也没有进入死路,就需要继续探索每一种可能的选择。根据上述的分析,我们可以编写以下伪代码来解释该回溯过程:

1
2
3
4
5
6
7
8
9
private static void explore(current(x, y), target(x, y)) {
if(一个解) {
打印出解
} else if(不是死路) {
explore(向 N 移动);
explore(向 E 移动);
explore(向 NE 移动);
}
}

在这个问题中,我们需要当前位置的 x, y 坐标和目标 x, y 的坐标。还要记录每次移动的结果,用来形成最终的路径报告。

我们可以通过对比当前移动的起点和终点是否匹配,来验证是否找到了解。对于是否进入死路这个问题,我们知道在移动的过程中,横坐标和纵坐标只会递增,所以一旦当前位置的 x 坐标值大于目标位置的 x 坐标值,或者当前位置的 y 坐标值大于目标位置的 y 坐标值,就能知道在相应方向上移动距离超过了目标值,所以永远不可能找到解,这时需要停止继续搜索。整合这些分析,我们可以得到以下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public static void main(String[] args) {

// 使用回溯法找到(1, 2)的所有线路
travel(1, 2);

}

/**
* 反应问题特性的参数的公有方法
*
* @param targetX :x 目标值
* @param targetY :y 目标值
*/
public static void travel(int targetX, int targetY) {
explore(targetX, targetY, 0, 0, "path: ");
}

/**
* 执行实际回溯处理过程的私有方法
*
* @param targetX :x 目标值
* @param targetY :y 目标值
* @param currX :当前 x 目标值
* @param currY :当前 y 目标值
* @param path :移动的路径
*/
private static void explore(int targetX, int targetY, int currX, int currY, String path) {
if (currX == targetX && currY == targetY) {
System.out.println(" 找到解:" + path);
} else if (currX <= targetX && currY <= targetY) {
explore(targetX, targetY, currX, currY + 1, path + " N");
explore(targetX, targetY, currX + 1, currY, path + " E");
explore(targetX, targetY, currX + 1, currY + 1, path + " NE");
}
}

输出结果

1
2
3
4
5
找到解:path:  N N E
找到解:path: N E N
找到解:path: N NE
找到解:path: E N N
找到解:path: NE N

下图则是上述搜索对应的决策树,其中五个深色的部分就是找到的解。
代码对应的决策树

这种返回到上一次选择并继续搜索其他可能性的特性,是讲该类方法成为回溯法的原因。找到解或者死路的时候,就返回上一次进行选择的情况,并尝试其他可能,直到尝试完所有可能的选择。


参考文章:

《Java 程序设计教程 第三版》