数据结构与算法学习笔记（1）——递归

发表于   |   分类于   |  

本章简单地讲一讲递归以及涉及到的问题。

本文仅供个人记录和复习，不用于其他用途

递归的概念

所谓的递归，最开始是由汉诺塔问题提出的。简单来讲，我们如果要解决一个大的问题，不妨先想一想小一点的问题如何解决。假如这个小问题也解决不了，那么就想一想更小的。将这个过程一直持续下去，那么总会出现一个最小的问题，能够被我们轻松解决。那么反过来，最大的问题也能够被层层推出，得到最终的答案。汉诺塔问题我就不再赘述了，这里只讲一讲其他有代表性的问题。

例题

用递归将数据转换成二进制

我们如何将一个十进制数转换成二进制数？步骤我们都知道，就是用短除法来转换。看一看短除法的过程，是不是有点像递归呢？

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
#include <stdio.h>
#include <stdlib.h>
void change(int n)
{
    if (n == 0)
        return 0;
    else
    {
        change(n / 2);
        printf("%d", n % 2);
    }
}
int main()
{
    int n;
    printf("请输入你要转换的十进制数：");
    scanf("%d", &n);
    getchar();
    printf("\n转换的结果为：");
    change(n);
    getchar();
}

我们使用短除法就是将数值除以2，保留每次的余数，一直到数值为0时，将余数倒序输出，就是该数值的二进制表达了。这里的change()递归调用之所以在printf()前面，是因为我们需要倒序输出，所以必须从最后一个余数开始输出。当然，这个程序不仅仅用于转换二进制，我们只需要修改一下，就能变成转换三进制或其他进制等等。

跳阶梯

这里有一个比较有意思的问题：现在有一个阶梯，你可以一次跨1阶或者2阶。如果这个阶梯有50阶，那么走完这个阶梯有多少种方法？不要被这个长长的阶梯给吓住了，试着将问题缩小：

  • 当阶梯数为1时，我们就只能跨1阶，共有1种方法
  • 当阶梯数为2时，我们既可以跨两次1阶，也可以跨2阶，共有2种方法

很显然，这两种情况就是阶梯问题的基本答案，我们递归时就要从这两个方面来寻找答案。如果我们想要走上第3阶，我们可以通过两种方式：

  • 从第1阶跨2阶
  • 从第2阶跨1阶

而当我们处在第1或第2阶时，答案已经知道了，所以共有1+2=3种方法。至于往上走，同样也是这种解决方法。通式：digui(n - 1) + digui(n - 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
double digui(int n)
{
    if (n == 1)
    {
        return 1;
    }
    else if (n == 2)
    {
        return 2;
    }
    else
    {
        return digui(n - 1) + digui(n - 2);
    }
}
double xunhuan(int n)
{
    double n1 = 1;
    double n2 = 2;
    double n3;
    int i;
    for (i = 0; i < n - 2; i++)
    {
        n3 = n1 + n2;
        n1 = n2;
        n2 = n3;
    }
    return n3;
}

对于3阶以上的，无非就是跨1阶还是跨2阶，所以将这两种情况相加即可。这里还给出来另外一种解法，那就是使用循环，不过这个循环其实就相当于递归中的三种情况。n3代表的是当前阶数所用的方法数，n2代表的是前1阶所用的方法数，n1代表的是前2阶所用的方法数，本质上就是不断往上移动。

这里要注意的是，数据类型使用的是double。其实对于50阶来说，总方法数很多，所以要使用double。另外，大家也不用真的去计算走到50阶有多少种方法，因为这个数值太大，一般的计算机无法在短时间内计算出来。

跳阶梯升级版

假如我们加大一下难度，我们一次可以跨1、2、…、n阶，那么跨上第n阶有多少种方法？这里不用急，我们一个个的看：

  • digui(1) = 1
  • digui(2) = digui(1)
  • digui(3) = digui(1) + digui(2)
  • digui(n - 1) = digui(1) + … + digui(n - 2)
  • digui(n) = digui(1) + … + digui(n - 2) + digui(n - 1)

请注意，digui(n - 1)其实就是digui(1) + … + digui(n - 2)，而这两者相加则等于digui(n)，也就是说digui(n)其实就是2 * digui(n - 1)。

1
2
3
4
5
6
7
8
9
10
11
double digui(int n)
{
    if (n == 1)
    {
        return 1;
    }
    else
    {
        return 2 * digui(n - 1);
    }
}

矩形覆盖

再来看一个问题：现在有无数个2×1的小矩形，以及一个2×n的大矩形（n为非负整数），请问要让小矩形不重叠的覆盖大矩形，共有多少种方法？问题看似复杂，其实也是斐波拉契数列的应用。小矩形有横和竖两种摆法，分情况讨论如下：

  • n = 0，0种方法
  • n = 1，1种方法
  • n = 2，2种方法
  • n = 3，f(2) + f(1)
  • n = n，f(n - 1) + f(n - 2)

当n为3时，我们可以竖着摆一个小矩形，然后剩下的就是f(2)。或者是横着摆两个小矩形，剩下的就是f(1)。当问题被扩展时，就成为了斐波拉契数列。

八皇后问题

这个问题比较经典，说的是在8×8的棋盘上，如果摆放上八个皇后，使得八个皇后之间没有冲突，问有多少种摆法。在国际象棋中，皇后能够向上下左右以及对角线等八个方向移动，也就是说八个皇后所能够移动的方向，都不能够有皇后出现。

其实这个问题并不复杂，既然是在8行8列的棋盘上放8个皇后，那么肯定每行每列都只能有一个皇后。也就是说，我们可以从第1行第1列开始摆放皇后，尝试它所有的可能，然后再尝试第2列等等。至于第2个皇后，自然就是在第1个皇后的基础上递归产生的。

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
#include <iostream>
#include <cstdio>
int a[100], n, count;
bool check_2 (int a[],int n)
{
    // 多次被调用，只需一重循环 
    for(int i = 1; i <= n - 1; i++)
    {
        if((abs(a[i] - a[n]) == n - i) || (a[i] == a[n]))
            return false;
    }      
    return true;
}
void backtrack(int k)
{
    if (k > n)//找到解
    {
        for(int i = 1; i <= 8; i++)  
        {
            cout << a[i];
        }
        cout << endl;
        count++;
    }
    else
    {
        for (int i = 1; i <= n; i++)
        {
            a[k] = i;
            if (check_2(a,k) == 1)
            {
                backtrack(k+1);
            }
        }
    }
    
}
void main()
{
    n = 8, count = 0;
    backtrack(1);
    cout << count << endl;
}

递归中的逻辑很简单，简单来讲就是从第一行第一列开始，往下探索所有的可能性，对每一个位置安排进行检验，不符合就尝试下一种可能。当达到最后一行，同时检验合格时，一个解就诞生了。当第一列的所有可能性探索完后，开始探索第一行第二列。总而言之，对于每一行，其实都是和第一行一样的，只不过这种循环是层层嵌套的：

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
void queens_2()
{
    int a[9];
    int count = 0;
    for(a[1] = 1; a[1] <= 8; a[1]++)
    {
        for(a[2] = 1; a[2] <= 8; a[2]++)
        {
            if (!check_2(a, 2))  continue;
            for(a[3] = 1; a[3] <= 8; a[3]++)
            {
                if (!check_2(a, 3))  continue;
                for(a[4] = 1; a[4] <= 8; a[4]++)
                {
                    if (!check_2(a, 4))  continue;
                    for(a[5] = 1; a[5] <= 8; a[5]++)
                    {
                        if (!check_2(a, 5))  continue;
                        for(a[6] = 1; a[6] <= 8; a[6]++)
                        {
                            if (!check_2(a, 6))  continue;
                            for(a[7] = 1; a[7] <= 8; a[7]++)
                            {
                                if (!check_2(a, 7))  continue;
                                for(a[8] = 1; a[8] <= 8; a[8]++)
                                {
                                    if (!check_2(a, 8))  
                                        continue;
                                    else
                                    {
                                        for(int i = 1; i <= 8; i++)  
                                        {
                                            cout << a[i];
                                        }
                                        cout << endl;
                                        count++;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout << count << endl;
}

事实上，所有的循环，都能够用递归来表示。但是呢，并不是所有的递归都能用循环来表示。不过，对于大部分情况，我们在理解递归时，可以适当的用循环的思想来辅助理解。递归相对于循环，大大地简化了代码量，不过逻辑没有循环那么清楚。