🤳概念

  • 递归边界 —— 分解的尽头
  • 递归式（递归调用） —— 将原问题分解为若干个子问题（分治）

递归多半会与深度广度优先搜索结合考察
因此切记要自己动手写全递归过程！！！

🐱‍🚀例题

  1. //简单款
  2. //Fibonacci  F0 = F1 = 1 F(n) = F(n-1) + F(n-2)
  3. int Fibonacci(int index){
  4.     if(index == 0 || index == 1) return 1;
  5.     else return Fibonacci(n-1)+Fibonacci(n-2);
  6. }

全排列

  1. //最经典 全排列 Full-Permutation
  2. const int maxn = 11;
  3. int n;
  4. int P[maxn],hashTable[maxn] = {false};
  5. //P is output of full permutation
  7. //generate permutation start with nuber index;
  8. void generateF(int index){
  9.     //recursion borden
  10.     if(index == n+1){
  11.         for(int i=1;i<=n;i++){
  12.             printf("%d ",P[i]);
  13.         }
  14.         printf("\n");
  15.         return;
  16.     }else
  17.     {
  18.         for(int x=1;x<=n;x++){
  19.             //对每个排列位(index)进行给定数列遍历,对每个递归分支,都用独立hashmap
  20.             //来记录该遍历数是否已插入排列
  21.             //递归边界是当下一递归式参数越界时,说明排列完成，输出并开始大返回
  22.             //递归边界“到达后”逐步返回重置hashmap达到独立hashmap
  23.             //注意全排列和组合的区别
  24.             if(hashTable[x]==false){
  25.                 P[index] = x; //notice the diff between index & x
  26.                 hashTable[x] = true;
  27.                 generateF(index+1);
  28.                 hashTable[x] = false;
  29.             }
  30.         }
  31.     }
  32. }
  33. main->generateP(1);
  35. example
  36. input:
  37. n = 3
  38. output:
  39. 1 2 3 
  40. 1 3 2 
  41. 2 1 3 
  42. 2 3 1 
  43. 3 1 2 
  44. 3 2 1

n皇后问题

image.png
假如用组合来枚举（n^2棋盘的n枚棋子）情况->筛选；需要C(n*n,n)，当n为8就是54502232次
因此用递归按行DFS，产生1-n的全排列，记录每个合法排列，需要n! 当n为8就是40320

  1. bool validQueen(){
  2.     for(int i = 1; i <= n; i++){
  3.         for(int j = i+1; j<=n; j++){
  4.             if(abs(P[i] - P[j])  == abs(i - j) || P[i] == P[j]){
  5.                 return false;
  6.             }
  7.         }
  8.     }
  9.     return true;
  10. }
  11. void generateP(int index){
  12.     if(index == n+1 && validQueen()){
  13.         for(int i = 1; i <= n; i++){
  14.             printf("%d ",P[i]);
  15.         }
  16.         printf("\n");
  17.         count++;
  18.         return;
  19.     }
  20. //else are the same
  21.     }
  22. }

组合

  1. //生成C(n,k)全组合
  2. //除了用到递归 还有 深度优先搜素
  3. int n,k,sum,res;
  4. int P[22] = {0};
  5. int A[22] = {0};
  6. void generateP(int curP,int curA){
  7.     if(curP == k+1){
  8.         //同样定义递归边界
  9.         //if(check(sum)) res++;
  10.         for(int i = 1; i <= k; i++){
  11.             printf("%d ",P[i]);
  12.         }
  13.         printf("\n");
  14.         return;
  15.     }
  16.         for(int i = curA; i <= n;i++){
  17.             //精髓在i = curA，实现排列的C(n,1)->C(n-1,1)->...选取
  18.             //初始逻辑为 通过gP(0,0) 产生 gp(1,1)-gp(1,n) 并以此深度搜索
  19.             //if判断在于控制只让gp(0,0)产生分支, 否则gp(0,1)->gp(1,2)
  20.             //等同于gp(0,0)->gp(1,2)
  21.             P[curP] = A[i];
  22.             if(curP == 0 && i != 0) return;
  23.             generateP(curP+1,i+1);
  24.             //sum -= A[i];
  25.         }
  26. }