算法设计思维之递归与八皇后问题

递归简介

计算机思维和人的思维最大的不同就是递归。我们日常思考问题方式是正向的递推（iterative），计算机是逆向的递归思维。要想真正理解的计算机解决问题的精髓，递归是必须要学的。

递推是人本能的正向思维，比如数数，从1、2、3一直数到100，这就是典型的递推。如果用递推的方法来计算一个数的阶乘，比如5! = 1×2×3×4×5，一个很自然的做法就是从小到大一个个乘起来。

但是，对于一些难题，递推方法并不好用，比如经典的八皇后问题。

八皇后问题

如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

按照我们通常的递推思维，可以在第一行摆好一个棋子，它当然不会和任何棋子冲突，然后第二行摆一个，保证它和第一个棋子没有冲突，然后再摆第三行的，以此类推。

需要指出的是，没有计算机之前找到所有可能的摆放是非常困难的。如果你能在5分钟内找到一个答案，就算非常快了。**大数学家高斯穷其一生只找到76种方案，而八皇后独立解共有92种。**当然，有了计算机，很快就能找到它的全部92种结果。

要更好的求解这个问题，就要用递归的思维。计算机计算阶乘，比如说计算5!，计算机就会把它变成 5×4!，4!不知道，没事，同样转化成4×3!，以此类推。最后到了1!（递归基），计算机知道它等于自身，就不接着往下扩展。接下来，计算机倒推回去所有结果，1!知道了，2!，然后3!，4!，5!。

递归的过程，从上向下层层展开，再从下到上一步步回溯。这和栈这种数据结构是一致的，即先进后出，后进先出，但栈清空的时候，计算就完成了。不过，这带来了新的问题。

递归执行的过程

要理解递归带来的问题，就要理解递归的工作过程，有必要先来看看C语言中函数执行的方式。基于这点，我们需要了解一点关于C程序在内存中的组织方式。基本上来说一个可执行程序由四个区域组成：代码段（.text）、静态数据区（.data）、堆（heap）和栈（stack）。

bss（block started by symbol）由符号开始的块。

• 代码段包含程序运行时所执行的机器指令。
• 静态数据区包含在程序生命周期内一直持久的数据，比如全局变量和静态局部变量。
• 堆包含程序运行时动态分配的存储空间，比如malloc分配的内存。
• 栈包含函调用的信息。

注意：按照惯例，堆的增长方向从程序低地址到高地址向上增长，而栈的增长方向刚好相反。（实际情况可能不是这样，和CPU的体系结构有关）。另外，这里的堆和数据结构的堆没有太大的关系。

当C程序中调用了一个函数时，栈中会分配一块空间来保存与这个调用相关的信息。每一个调用都被当作是活跃的。栈上的那块存储空间称为活跃记录，或者称为栈帧。栈帧由5个区域组成：输入参数、返回值空间、计算表达式用到的临时存储空间、函数调用时保存的状态信息以及输出参数。

输入参数是传递到活跃记录中的参数；输出参数是传递给在活跃记录中调用的函数。一个活跃记录中的输出参数就成为栈中下一个活跃记录的输入参数（到了1!=1，1就作为输出参数输出到调用1!的2!）。函数调用产生的活跃记录将一直存在于栈中直到这个函数调用结束。

// 阶乘的递归实现
int fact(int n) {
  if (n < 0) return 0;
  else if (n == 0) return 1;
  else if (n == 1) return 1;
  else
    return n * fact(n - 1);
}

考虑一下计算4!发生了什么。
初始调用fact(4)会在栈中产生一个活跃记录，输入参数n=4，由于这个调用没有满足函数的终止条件，因此fact将继续以n=3为参数递归调用。这将在栈上创建另一个活跃记录，这次输入参数是3。这里，n=3也是第一个活跃期中的输出参数，因为正是在第一个活跃期调用fact产生了第二个活跃期。这个过程将一直持续，直到n的值变为1。

此时，满足终止条件，fact将返回1。一旦n=1的活跃期结束，n=2的递归计算结果就是2×1=2，这是n=2的活跃期也将结束，返回值2。结果就是n=3的递归计算结果表示为3×2=6，返回值6。最终，当n=4递归结果表示为6×4=24，n=4的活跃期将结束，返回值24。函数已经从最初的调用中返回，递归过程结束。

栈是用来存储函数调用信息的绝好方案，这也是由于其后进先出的特点满足了函数调用和返回的顺序。然而，使用栈也有一些缺点。**栈维护了每个函数调用的信息直到函数返回后才释放，这需要占用相当大的空间，尤其是在程序中使用了许多递归调用的情况下。**除此之外，因为有大量的信息需要保存和恢复，因此生成和销毁活跃记录需要耗费一定的时间（简而言之，调用函数需要开销）。一旦函数调用的开销变得很大的时候，我们就需要考虑用循环（迭代）的方案。

幸运的是，我们可以采用一种称为尾递归的特殊递归方式来避免前面的提到的缺点。

尾递归

如果一个函数中所有的递归形式的调用都出现在函数的末尾，递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，我们称这个递归函数是尾递归的。尾递归函数的特点是在回归过程中不用做任何操作。这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。

当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活跃记录而不是在栈中去创建一个新的。这样所使用的栈空间就大大缩减，实际的运行效率也会更高。

// 尾递归实现
int fact(int n, int a) {
  if (n < 0) return 0;
  else if (n == 0) return 1;
  else if (n == 1) return a;
  else
    return fact(n - 1, n * a);
}

定义了第二个参数a，用来维护递归的深度。这样就避免了每次还要将返回值再乘以n。递归调用后，直接返回a即可。回归过程不需要任何操作，这是所有尾递归函数的标志。

八皇后问题的解法

有了递归的方法后，就很容易解决“八皇后”问题了。具体的做法如下：

1. 加入棋盘上已经有7个皇后，它们彼此的位置不冲突，那么在第八行从第1个位置到第8个位置一一验证即可。当然，你会问前面七个皇后怎么摆，才能保证它们彼此不冲突呢？很简单，按照第八个皇后这个做法照猫画虎地做。
2. 当棋盘上一个棋子都没有的时候，从第一行的第一个位置到第八个位置一个个分别试一遍。

当然，在这个过程中，有的摆放往后可以走得通，有些走不通。如果走不通，计算机会直接跳到下一个位置去试验。实际上在4万多种摆法中，只有92个行得通。

具体实现

1. 最简单的思路：（纯暴力）64个格子中选一个子集 x
2. 进一步：从64个格子中选8个格子放皇后，组合生成，C(64,8)=4.426*10^9，还是不够好
3. 再进一步：C[x]表示第x行皇后的列编号，问题就变成排列生成0～7的排列只有8!=40320，可以直接枚举

// 八皇后问题
#include <cstdio>
const int kMaxN = 8;

int C[kMaxN]; // 皇后的列编号
int n;
int tot;

void Search(int cur) {
  if (cur == n) {
    ++tot; // 递归边界。所有皇后必然不冲突，找到解
  } else for (int i = 0; i < n; i++) {
      bool ok = true;
      C[cur] = i; // 尝试把第cur行的皇后放在第i列
      // 检查是否和前面的皇后冲突
      for (int j = 0; j < cur; j++) {
        // 既然是逐行放置，皇后肯定不会横向攻击
        if (C[cur] == C[j] || cur - C[cur] == j - C[j] ||
            cur + C[cur] == j + C[j]) {
          // 检查是否同一条对角线上
          // y - x 标识主对角线
          // x + y 标识副对角线
          ok = false;
          break;
        }
      }
      if (ok) Search(cur + 1); // 如果合法，则继续递归
    }
}

// 表示已经放置的皇后占据了哪些列、主对角线、副对角线
bool vis[3][2 * kMaxN];

// 结点数很难进一步减少了，但程序的效率还能进一步提高
// 二维数组vis[2][]直接判断当前尝试的皇后所在的列和
// 两个对角线是否已经有其他皇后
// y - x有可能为负，所以要加上n
void SearchAdvance(int cur) {
  if (cur == n) {
    ++tot; // 递归边界。所有皇后必然不冲突，找到解
  } else for (int i = 0; i < n; i++) {
      // !vis[0][i] && !vis[1][cur + i] && !vis[2][cur - i + n]
      // 可以用德摩根律化简
      if (!(vis[0][i] || vis[1][cur + i] || vis[2][cur - i + n])) {
        // 利用二维数组直接判断
        C[cur] = i; // 如果不用打印解，可以省略C数组
        // 修改全局变量
        vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = true;
        SearchAdvance(cur + 1);
        // ！！！切记！！！一定要改回来！
        vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = false;
      }
    }
}

int main() {
  n = 8;
  SearchAdvance(0);
  printf("%d\n", tot);
  return 0;
}

1. 如果在回溯法中使用了辅助的全局变量，则一定要及时恢复原状。
2. 特别地，若函数有多个出口，则需要在每个出口处恢复被修改的值。
3. 判断当前皇后是否相互冲突，并不判断以前的皇后是否冲突————这在之前已经判断过了。

总结

• 递归是计算机解决问题的精髓

• 递归的本质有两条

  • 自顶向下（从整体到局部）；
  • 自己不断重复；

• 递归结构有着内在和谐的美感，子问题的结构和最终问题的结构是同构的

• 深层次递归会带来空间消耗过大的问题

• 可以通过尾递归来优化递归算法