概念

学习使用递归的前提： 函数理解深入（带参的函数，有返回值的函数，函数的嵌套(就是“自身调用自身”)） 操作时，试验无限递归 递归的终止条件 “回溯时还原现场”保证执行前后程序面对问题的状态是相同的。

递归是程序遍历状态空间的基本方式。
以“原问题”为起点，尝试寻找把状态空间缩小到已知的“问题边界”的路线。
再通过该路线反向回溯的遍历方式，就是递归。

程序在每个步骤应该面对相同种类的问题，这些问题都是原问题的一个子问题，可能仅在规模或者某些限制条件上有所区别，并且能够使用“求解原问题的程序”进行求解。程序在执行变换操作执行三个操作：

  1. 缩小问题状态空间的规模。程序尝试寻找在 “原问题” 与 “问题边界” 之间的变换路线，并向正在探索的路线上迈进一步。
  2. 尝试求解规模缩小以后的问题，可能成功，可能失败。
  3. 如果成功，即找到了规模缩小后的问题的答案，那么将答案扩展到当前问题。如果失败，那么重新回到当前问题，程序可能会继续寻找当前问题的其他变换路线，直到最终确定当前问题无法求解。

在使用枚举算法蛮力搜索问题的整个“状态空间”时，经常需要递归。
枚举算法，就是遍历一遍，逐个举例。
初级的枚举很简单，就是for循环的应用，高级的就很难了，复杂在题目理解和遍历的操作方式

Thinking recursively is natural, but need good amount of training.

image.png

  1. void TriangleRev(int x) {
  2.    if (x <= 0) return;
  4.    for (int i = 1; i <= x; i++)
  5.         cout << "*";
  7.     cout << endl;
  9.     TriangleRev(x - 1);
  10. }
  12. /*
  13. Call TriangleRev(7)
  14. TriangleRev(7) <-- prints 7 stars & new line
  15.   TriangleRev(6) <-- prints 6 stars & new line
  16.     TriangleRev(5) <-- prints 5 stars & new line
  17.       TriangleRev(4) <-- prints 4 stars & new line
  18.         TriangleRev(3) <-- prints 3 stars & new line
  19.           TriangleRev(2) <-- prints 2 stars & new line
  20.             TriangleRev(1) <-- prints 1 star & new line
  21.               TriangleRev(0) <-- base case
  22.             TriangleRev(1)
  23.           TriangleRev(2)
  24.         TriangleRev(3)
  25.       TriangleRev(4)
  26.     TriangleRev(5)
  27.   TriangleRev(6)
  28. TriangleRev(7)
  30. The output will be:
  31. *******
  32. ******
  33. *****
  34. ****
  35. ***
  36. **
  37. *
  39. */

image.png

  1. void Triangle(int x) {
  2.    if (x <= 0) return;
  4.    Triangle(x - 1);
  6.    for (int i = 1; i <= x; i++)
  7.         cout << "*";
  8.    cout << endl;
  9. }
  12. /*
  13. Call Triangle(7)
  14. Triangle(7)
  15.   Triangle(6)
  16.     Triangle(5)
  17.       Triangle(4)
  18.         Triangle(3)
  19.           Triangle(2)
  20.             Triangle(1)
  21.               Triangle(0) <-- base case
  22.             Triangle(1) <-- prints 1 star & new line
  23.           Triangle(2) <-- prints 2 stars & new line
  24.         Triangle(3) <-- prints 3 stars & new line
  25.       Triangle(4) <-- prints 4 stars & new line
  26.     Triangle(5) <-- prints 5 stars & new line
  27.   Triangle(6) <-- prints 6 stars & new line
  28. Triangle(7) <-- prints 7 stars & new line
  30. The output will be:
  32. *
  33. **
  34. ***
  35. ****
  36. *****
  37. ******
  38. *******
  39. */

How to trace recursion

  1. // Factorial(n) = n * Factorial(n-1).        
  2. // Factorial(0) = Factorial(1) = 1
  4. int Fact(int n)
  5. {
  6.     if(n <= 1)
  7.         return 1;
  9.     return n * Fact(n-1);
  10. }
  12. /*
  13. Fact(4)
  14.     4* Fact(3)
  15.         3* Fact(2)
  16.             2* Fact(1)
  17.             2* 1 <-- 2
  18.         3* 2 <-- 6
  19.     4* 6 <-- 24
  20. */
  1. void printNumber(int n)    // for n > 0
  2. {    // 1234567
  3.     if(n)
  4.     {
  5.         printNumber(n/10);  // 214/10 = 21
  6.         cout<<n%10;         // 214%10 = 4
  7.     }
  8. }
  10. // E.g. 7 = 111        214 = 11010110
  11. // If number%2 get for us last bit in binray representation
  12. // If we could print last bit, we could print
  13. void printNumberBits(int n)    // for n > 0
  14. {
  15.     if(n)
  16.     {
  17.         printNumberBits(n/2);    // 214/2 = 1101011  last bit removed
  18.         cout<<n%2;              // 214%2 = 0
  19.     }
  20. }

入门例题

爬楼梯
  1. // 理解推导公式后，利用递归实现

菲波那契数列
  1. // 理解推导公式后，利用递归实现

Pell数列
  1. // 需要使用记忆化

Complete search

在学习递归之后，我们就学会了遍历问题状态空间的一种方式方法。这样我们就可以去尝试搜索这个问题的状态空间。这里，我们先来接触Complete search（也可以理解为暴力搜索）

Complete search is a general method that can be used to solve almost any algorithm problem. The idea is to generate all possible solutions to the problem using brute force, and then select the best solution or count the number of solutions, depending on the problem.

Complete search is a good technique if there is enough time to go through all the solutions, because the search is usually easy to implement and it always gives the correct answer. If complete search is too slow, other techniques, such as greedy algorithms or dynamic programming, may be needed.

例题:生成子集

For example, the subsets of {0,1,2} are 空集, {0}, {1}, {2}, {0,1}, {0,2}, {1,2} and {0,1,2}.

  1. //An elegant way to go through all subsets of a set is to use recursion
  2. void search(int k) {
  3.     if (k == n) {
  4.        // 问题的边界
  5.        // process subset
  7.        return ;
  8.     } 
  10.     //不选
  11.     search(k+1);
  13.     //选
  14.     subset.push_back(k);
  15.     search(k+1);
  16.     subset.pop_back(); 
  17. }
  19. search(0); //调用
  20. //这个就是递归枚举子集

The following tree illustrates the function calls when n = 3. We can always choose either the left branch (k is not included in the subset) or the right branch (k is included in the subset).
（注意反复学习这个搜索树的执行过程）
image.png

  1. // 位运算枚举子集
  3. // Each subset of a set of n elements can be represented as a sequence of n bits, 
  4. // which corresponds to an integer between 0...2n −1. 
  5. // The ones in the bit sequence indicate which elements are included in the subset.
  7. //上面的程序，我们使用了一个vector来存储选了什么数字
  8. //这里，我们来学习一下位运算的枚举子集
  9. //这是一个拓展
  11. for (int b = 0; b < (1<<n); b++) {
  12.     vector<int> subset;
  13.     for (int i = 0; i < n; i++) {
  14.        if (b&(1<<i)) subset.push_back(i);
  15.     }
  16. }

例题:生成排列

For example, the permutations of {0,1,2} are (0,1,2), (0,2,1), (1,0,2), (1,2,0), (2,0,1) and (2,1,0).

  1. // Each function call adds a new element to permutation. 
  2. // The array chosen indicates which elements are already included in the permutation.
  3. // If the size of permutation equals the size of the set, a permutation has been generated.
  5. void search() {
  6.     if (permutation.size() == n) {
  7.        // process permutation
  9.         return ;
  10.     }
  12.     for (int i = 0; i < n; i++) {
  13.         if (chosen[i]) continue;
  15.         chosen[i] = true;
  16.         permutation.push_back(i);
  17.         search();
  18.         chosen[i] = false;
  19.         permutation.pop_back();
  20.     }
  21. }
  23. search(); //调用
  1. // The C++ standard library contains the function next_permutation 
  2. // that can be used for this
  4. vector<int> permutation;
  5. for (int i = 0; i < n; i++) {
  6.     permutation.push_back(i);
  7. }
  8. do {
  9.     // process permutation
  11. } while (next_permutation(permutation.begin(),permutation.end()));

《进阶指南》题目

例题:递归实现指数型枚举

子集枚举

  1. vector<int> chosen;
  3. void dfs(int x)
  4. {
  5.     if (x == n + 1)   //也可以写x > n
  6.     {
  7.         for (int i = 0; i < chosen.size(); i++)
  8.             printf("%d ", chosen[i]);
  9.         puts("");
  11.         return ;
  12.     }
  14.     //问：先不选x， 还是先选x。会影响我们的输出顺序
  15.     //观察样例，我们先不选x
  17.     //不选x，求解子问题
  18.     dfs(x + 1);
  20.     //选x，求解子问题
  21.     chosen.push_back(x);
  22.     dfs(x + 1);
  23.     chosen.pop_back();  //回溯还原现场
  24. }
  1. //位运算版本，这是进阶的
  2. void dfs(int u, int state)
  3. {
  4.     if (u == n)
  5.     {
  6.         for (int i = 0; i < n; i++)
  7.             if (state >> i & 1)
  8.                 cout << i + 1 << ' ';
  9.         puts("");
  11.         return ;
  12.     }
  14.     //求解子问题
  15.     dfs(u + 1, state);          //不选，state初始是0，等价于dfs(u + 1, state & (~(1 << u)));
  16.     dfs(u + 1, state | 1 << u); //选
  17. }

例题:递归实现组合型枚举

在子集枚举的基础上，进行剪枝

  1. vector<int> chosen;
  3. void dfs(int x)
  4. {
  5.     if (chosen.size() > m || chosen.size() + (n - x + 1) < m) return ;
  7.     if (x == n + 1)
  8.     {
  9.         //如何输出状态
  10.         for (int i = 0; i < chosen.size(); i++)
  11.             printf("%d ", chosen[i]);
  12.         puts("");
  14.         return ;
  15.     }
  17.     //选x
  18.     chosen.push_back(x);
  19.     dfs(x + 1);
  20.     chosen.pop_back();
  22.     //不选x
  23.     dfs(x + 1);
  24. }
  1. //递归实现，枚举的时候带着顺序
  2. void get_combination(int u, int last)
  3. {
  4.     if (u == m){
  5.         for (int i = 0; i < m; i++) printf("%d ", chosen[i]);
  6.         puts("");
  7.     }
  9.     for (int j = last + 1; j <= n; j++){
  10.         chosen.push_back(j);
  11.         get_combination(u + 1, j);
  12.         chosen.pop_back();
  13.     }
  14. }
  1. //位运算版本，这是进阶的
  2. //state表示状态
  3. void dfs(int u, int sum, int state)
  4. {
  5.     if (sum > m || sum + n - u < m) return ;
  7.     if (sum == m)
  8.     {
  9.         for (int i = 0; i < n; i++)
  10.             if (state >> i & 1)
  11.                 cout << i + 1 << ' ';
  12.         puts("");
  14.         return ;
  15.     }
  17.     dfs(u + 1, sum + 1, state | 1 << u);
  18.     dfs(u + 1, sum    , state         );
  19. }

例题:递归实现排列型枚举

排列枚举

  1. //用数组存方案
  2. //注意一下 0-index，如果是 1-index 呢？递归的边界是....什么？(提问)
  4. void dfs(int k)
  5. {
  6.     if (k == n)
  7.     {
  8.         for (int i = 0; i < n; i++)
  9.             cout << order[i] << ' ';
  10.         puts("");
  11.     }
  13.     for (int i = 1; i <= n; i++)
  14.     {
  15.         if (chosen[i]) continue;
  17.         order[k] = i;
  18.         chosen[i] = true;
  19.         dfs(k + 1);
  20.         chosen[i] = false;
  21.     }
  22. }
  1. // 用vector来存方案，用二进制数来记录状态
  2. vector<int> path;
  3. void dfs(int u, int state)
  4. {
  5.     if (u == n)
  6.     {
  7.         vector<int>::iterator i;
  8.         for (i = path.begin(); i < path.end(); i++)
  9.             cout << *i << ' ';
  10.         puts("");
  11.     }
  13.     for (int i = 0; i < n; i++)
  14.         if (!(state >> i & 1))
  15.         {
  16.             path.push_back(i + 1);   //用vector来记录方案
  17.             dfs(u + 1, state | 1 << i);
  18.             path.pop_back();
  19.         }
  20. }

NOIP 2012 普及组初赛试题，排列数

排列数 输入两个正整数n，m（1<n<20,1<m<n），在1~n中任取m个数，按字典序从小到大输出所有这样的排列。

  1. //用贪心的方法，贪出来字典序
  2. #include <bits/stdc++.h>
  4. using namespace std;
  6. const int N = 110;
  8. int data[N];
  9. bool used[N];
  10. int n, m;
  12. int main()
  13. {
  14.     cin >> n >> m;
  16.     //第一种方案存了起来
  17.     for (int i = 1; i <= m; i++){
  18.         data[i] = i;
  19.         used[i] = true;
  20.     }
  22.     bool flag = true;
  23.     while (flag){
  24.         //输出方案
  25.         for (int i = 1; i <= m; i++) cout << data[i] << ' ';
  26.         puts("");
  28.         flag = false;
  29.         for (int i = m; i >= 1; i--){
  30.             used[data[i]] = false;
  32.             for (int j = data[i] + 1; j <= n; j++){
  33.                 if (used[j] == false){
  34.                     data[i] = j;
  35.                     used[j] = true;
  37.                     flag = true;
  38.                     break;
  39.                 }
  40.             }
  42.             if (flag){
  43.                 for (int k = i + 1; k <= m; k++)
  44.                     for (int j = 1; j <= n; j++)
  45.                         if (used[j] == false){
  46.                             used[j] = true;
  47.                             data[k] = j;
  48.                             break;
  49.                         }
  51.                 break;
  52.             }
  53.         }
  54.     }
  56.     return 0;
  57. }

《一本通》题目

【例4.5】集合的划分
  1. //{an}是k子集合中的一个,S(n-1, k-1)
  2. //{an}不是k子集合中的任意一个子集，an与其他元素构成了子集，问题相当于S(n-1,k)。把an加入到k个子集中的任意一个中，有k种加入的方法

【例4.6】数的计数(Noip2001)
  1. //子问题是[1...x/2]
  2. for (int i = 1; i <= x / 2; i++){
  3.         dfs(i);
  4.         h[x] += h[i];
  5. }

逆波兰表达式
  1. //* a b
  2. //读入的是*号，我们就返回 dfs() * dfs()
  4. //这个题目的难点是string转double，如何转

全排列
  1. //前面的例题

分解因数
  1. //求的是分解的方案数， 有两种分析的方法
  3. //1. dfs(x, y)，调用时dfs(x, 2)，从2开始向上搜索x的约数
  4.     边界是x==1        
  5.     for (int i = y; i <= x; i++)  //从y往上找x的约数，如果找到，就求解子问题dfs(x/i, i)
  6.         if (x % i == 0) res += dfs(x / i, i);
  8. //2. dfs(a, b)，从b开始向下搜索a的约数，调用时dfs(x, x)
  9.     边界是a == 1 和 b == 1
  10.     如果a % b == 0，我们就 res += dfs(a / b, b); 把这个约数除掉，求解子问题
  11.     如果a % b != 0，我们就 dfs(a, b - 1); 往下看子问题

菲波那契数列
  1. //

Pell数列
  1. //

扩号匹配问题
  1. //模拟搜索的过程，用递归实现这个搜索的模拟过程（这个就不是什么数字上的往深层次递归了，这是模拟）
  2. //遇到左括号，就先标记上
  3. //遇到右括号，就从当前位置往前找“有标记的左括号”
  4. //找到了，就取消左括号的标记；没找到，就把这个右括号，标记起来

爬楼梯
  1. //

汉诺塔问题
  1. //

放苹果
  1. //把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
  2. //这道题目意义深远，打个星号
  3. //分情况讨论，盘子比苹果多的情况，苹果比盘子多的情况

求最大公约数问题
  1. //介绍GCD模板

2的幂次方表示
  1. //这道题比较复杂，作为拓展学习，涉及位运算，对理解二进制数有帮助
  2. //先分析一下边界
  3. //然后找到小于等于这个数的2的最大幂次，可能还有一个尾巴剩余
  4. //对幂次进行递归处理

分数求和
  1. //模拟两个分数相加的过程，通分和约分
  2. //约分的时候用到GCD

因子分解
  1. //分解质因数

判断元素是否存在
  1. //用递归遍历问题的状态空间，进行暴力枚举
  2. //这个也是模拟，递归往远处模拟排查