记录生活中的点点滴滴

0%

递归

发表于 Valine：

递归

递归可能不算难，但是我现在也不敢说我掌握了它。所以，再学习记录一下。

递归说到底，就是自己调用自己，是一种无穷迭代思维方式，简单粗暴的罗列。

递归对程序员的修养要求极高，无穷递归、栈溢出，各种问题，安全性比较难把握。

我们最好少用递归，能™for循环、堆栈什么数据结构解决的，别用递归这破玩意，墨迹。

递归的三大要素

第一要素：明确你这个函数想要干什么

第二要素：寻找递归结束条件

第三要素：找到函数的等价关系式

几个案例

我们通过下面的一些案例，再巩固一下：

斐波那契数列

斐波那契数列的是这样一个数列：1、1、2、3、5、8、13、21、34…，即第一项 f(1) = 1,第二项 f(2) = 1…,第 n 项目为 f(n) = f(n-1) + f(n-2)。求第 n 项的值是多少

第一，定义函数，明确我们要干什么？

1
2
3
public static int fib(int n){//fib是求第n项的值
    
}

第二，找到递归结束的条件

显然，当我们n为1或2的时候，结果fib(1) = fib(2) = 1，所以，递归结束条件：

1
2
3
4
public static int fib(int n){
    if(n<=2)
        return 1;
}

第三，找到等价函数关系式

题目已经给我们了： f(n) = f(n-1) + f(n-2)，用代码表示即可：

1
2
3
4
5
6
7
public static int fib(int n){
    //递归结束的条件
    if(n<=2)
        return 1;
    //等价函数关系式
    return fib(n-1)+fib(n-2);
}
小青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法

第一，定义函数，明确我们要干什么？

1
2
3
public static void f(int n){//f即求该青蛙跳上一个n级的台阶总共有多少种跳法
    
}

第二，找到递归结束的条件

找递归结束的条件，我们把n压缩到最小，即如果当n为1时，那么只有1种跳法。但是别忘了，这道题它还可以跳两级。当n为2的时候也是一个结束条件，此时有几种跳法？2种呗。所以，上代码：

1
2
3
4
5
6
public static int f(int n){
    if(n==1)//1个台阶的时候，只有1种方法
        return 1;
    if(n==2)
        return 2;//2个台阶的时候，有2种方法
}

第三，找到等价函数关系式

青蛙跳了n阶，其实它有两种方法：

  • 跳1阶加f（n-1）
  • 跳2阶加f（n-2）

所以等价函数关系式就是：f(n) = f(n-1)+f(n-2)

所以总的代码就是：

1
2
3
4
5
6
7
public static int f(int n){
    if(n==1)//1个台阶的时候，只有1种方法
        return 1;
    if(n==2)
        return 2;//2个台阶的时候，有2种方法
    return f(n-1)+f(n-2);//有两种选择：1.跳1阶加f（n-1）2.跳2阶加f（n-2）
}

有关递归的一些优化思路

1、考虑是否重复计算

如果你使用递归的时候不进行优化，是有非常非常非常多的子问题被重复计算的。

啥是子问题？ f(n-1),f(n-2)…就是 f(n) 的子问题了。

例如对于小青蛙那道题，f(n) = f(n-1) + f(n-2)。递归调用的状态图如下：

看到没有，递归计算的时候，重复计算了两次 f(5)，五次 f(4)。。。。这是非常恐怖的，n 越大，重复计算的就越多，所以我们必须进行优化。

如何优化？一般我们可以把我们计算的结果保证起来，例如把 f(4) 的计算结果保证起来，当再次要计算 f(4) 的时候，我们先判断一下，之前是否计算过，如果计算过，直接把 f(4) 的结果取出来就可以了，没有计算过的话，再递归计算。

用什么保存呢？可以用数组或者 HashMap 保存，我们用数组来保存把，把 n 作为我们的数组下标，f(n) 作为值，例如 arr[n] = f(n)。f(n) 还没有计算过的时候，默认a[n]为0。

当我们要判断的时候，如果 a[n] = 0，则证明 f(n) 没有计算过，否则， f(n) 就已经计算过了，且 f(n) = a[n]。直接把值取出来就行了。代码如下：

1
2
3
4
5
6
7
8
9
10
static int[] a = new int[10000];//数组，默认全部为0
//小青蛙案例，V2.0，用数组保存
public static int f(int n){
    if(n<=2)
        return n;
    if(a[n]!=0)
        return a[n];
    a[n] = f(n-1)+f(n-2);
    return a[n];
}

main方法进行测试，我们让n从1开始到45，再多int就溢出了。我们顺便再看看耗时：

1
2
3
4
5
6
7
8
public static void main(String[] args) {
    long start = System.currentTimeMillis();
    for (int i = 1; i < 46; i++) {
        System.out.println(f(i));
    }
    long end = System.currentTimeMillis();
    System.out.println("耗时："+(end-start));
}

运行结果如下：

这样肯定缩短时间了，你信不？不然我们用原来的递归测试一下，也是从1到45，看看运行时间：

太™狠了，我点开始之后，它运行 了5s才停下来，哈哈哈。

斐波那契数列那个例子和小青蛙好像一样，我们也可以用这种方式去优化它。

2、考虑是否可以自底向上

对于递归的问题，我们一般都是从上往下递归的，直到递归到最底，再一层一层着把值返回。

不过，有时候当 n 比较大的时候，例如当 n = 10000 时，那么必须要往下递归10000层直到 n <=1 才将结果慢慢返回，如果n太大的话，可能栈空间会不够用。

对于这种情况，其实我们是可以考虑自底向上的做法的。例如我知道

f(1) = 1;

f(2) = 2;

那么我们就可以推出 f(3) = f(2) + f(1) = 3。从而可以推出f(4),f(5)等直到f(n)。因此，我们可以考虑使用自底向上的方法来取代递归，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//自底向上
public static int f(int n){
    if(n<=2)
        return 1;
    int f1 = 1;
    int f2 = 1;
    int sum = 0;
    for (int i = 3; i <= n; i++) {
        sum = f1+f2;
        f1 = f2;
        f2 = sum;
    }
    return sum;
}

这个我们好像也可以用一个数组去避免重复计算，提高时间，但是感觉效果不是很明显。可能这个没有去用递归吧。可以看出，递归还是挺吓人的，太™磨叽了。

八皇后问题

八皇后问题（英文：Eight queens），是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。

问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。计算机发明后，有多种计算机语言可以编程解决此问题。

  1. 第一个皇后先放第一行第一列
  2. 第二个皇后放在第二行第一列、然后判断是否OK，如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适
  3. 继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解
  4. 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到
  5. 然后回头继续第一个皇后放第二列，后面继续循环执行1,2,3,4的步骤

其实主要函数就两个，一个是放置第n个皇后的 check 方法，另外一个是判断当前我们放置的第n个皇后和前面的已经摆好的皇后是否冲突的 judge 方法。

我们先要写check方法，在这一行使用一个for循环测试每一列的情况，循环内进行judge判断，如果不冲突则递归进行下一个check方法，否则进行下一个for的遍历。

总的代码如下：

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//八皇后问题
public class EightQueue {
    //定义一共多少个皇后
    int max = 8;
    //定义数组，保存皇后位置放置的结果，比如arr={0,4,7,5,2,6,1,3}
    int[] arr = new int[max];
    //定义总共的种类数
    static int count = 0;
    public static void main(String[] args) {
        EightQueue eightQueue = new EightQueue();
        eightQueue.check(0);
        System.out.println("方案种类数："+count);
    }
    //编写一个方法，放置第n个皇后
    public void check(int n){
        if(n==8){
            print();
            return;
        }
        //依次放入皇后，并判断是否冲突
        for (int i = 0; i < max; i++) {
            //先把当前这个皇后n，放到该行的第1列
            arr[n] = i;
            //判断是否冲突
            if(!judge(n)){//不冲突
                check(n+1);
            }
            //如果冲突就继续下一个循环
        }
    }
    //查看当我们放置第n个皇后,就去检测该皇后是否和前面已经摆放的皇后冲突
    public boolean judge(int n){
        /**
         * arr[i] == arr[n]表示在同一列
         * n-i == Math.abs(arr[n]-arr[i])表示在同一斜线
         */
        for (int i = 0; i < n; i++) {
            if(arr[i]==arr[n] || Math.abs(n-i)==Math.abs(arr[n]-arr[i]))
                return true;
        }
        return false;
    }
    //输出方法
    private void print() {
        count++;
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }
}