☘前言☘
最近发现自己还是太菜了，所以计划刷一遍算法笔记。 最近的计划是花两个月的时间，在回所之前把算法笔记刷完，不知道能不能实现了了，希望大家监督我，最近疫情好严重，被封校了，大家也要注意安全呀。
今天继续更新，昨天的hash表大家都用明白了么，今天我们来看看递归，希望大家能和我一起学习呀。每篇文章后面都有对应的练习题哦，我自己会写题解给大家作为参考，好了不bb了，我们开始把！
🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
📔源码地址：https://gitee.com/xingleigao/algorithm-notes
⏳全文大约阅读时间： 120min(有点长，大家忍一下 ，一定会有蜕变的)
文章目录
☘前言☘
👻1.分治
😶🌫️2.递归
2.1 求阶乘
2.2 Fibonacci数列求解
2.3全排列的求解
2.4 n皇后问题
推荐专栏
🐳课后习题
👻1.分治
我们经常听到大事化小、小事化了，这就是分治思想。准确表述是将原问题划分成若干个规模小而结构与原问题相同或相似的子问题，然后分别解决这些子问题，最后合并子问题的解，即可得到原问题的解，从上面的描述我们可以将这类问题解法分为三步，打开冰箱，塞进冰箱，关闭冰箱（不是）
1.分解： 将原问题分解为若干和原问题拥有相同或相似结果的子问题。（递归入口）
2.解决： 递归求解所有子问题。如果存在子问题的规模小到可以直接解决，就直接解决。（递归出口）
3.合并： 将子问题的解合并为原问题的解。(递归返回值)
一般来说分治思想既可以用递归实现，也可以通过非递归的手段去实现。
😶🌫️2.递归
如果你要理解递归，你要先理解递归，直到你能理解递归。感觉这句话很有意思，哈哈哈，递归的实现就是反复调用自身函数，直到问题减小到可以直接求解，返回求解结果。
这里面有两个重要的概念：
递归边界（我喜欢叫递归出口）
递归式（递归调用）
2.1 求阶乘
说了这么多概念，其实没有那么复杂 我们看一个求n ! n!n!的例子：
int F(int n){ if(n == 0); return 1; //(1) else return F(n - 1)*n; //(2) }
(1) . 递归出口 也就是问题的可求解的边界
(2). 递推式 其实就是f(n)=n∗f(n−1)
以求f ( 3 ) f(3)f(3)为例，求解过程中其实就是f(3)=f(2)∗3=f(2)∗2∗3=f(1)∗1∗2∗3=f(0)∗1∗1∗2∗3=1∗1∗2∗3
2.2 Fibonacci数列求解
F i b o n a c c i FibonacciFibonacci数列，就是求解F ( n ) = F ( n − 1 ) + F ( n − 2 ) F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2),其中F ( 1 ) = 1 , F ( 0 ) = 1 F(1) = 1, F(0) = 1F(1)=1,F(0)=1。
这就是典型的递归应用，看看代码：
int F(int n){ if(n == 0 || n == 1) return 1; //(1) return F(n-1) + F(n-2) //(2) }
同样对应有递归出口和递推式，所以递归的灵魂就是递归出口和递推式。
2.3全排列的求解
求一个序列的全排列，就可以划分一下以1元素开头的，以2元素开头....blabla，我们先填第一个，然后接下来利用上节课的hash表来记录已经插入的元素。然后递归求解。
示例题目：46. 全排列
int P[7],HashTable[22]; void generteP(int index,int* nums, int numsSize, int* returnSize, int** >returnColumnSizes,int** ans){ if(index == numsSize+1){ //（1） ans[*returnSize] = malloc(sizeof(int) * numsSize); memcpy(ans[*returnSize],P + 1,sizeof(int) * numsSize);//拷贝数据 (*returnColumnSizes)[*returnSize] = numsSize; (*returnSize)++; return; } for( int i = 0; i < numsSize;++i){ if(HashTable[nums[i] + 10] == false){ P[index] = nums[i]; //加入当前全排列 HashTable[nums[i] + 10] = true;//（2） generteP(index + 1, nums, numsSize,returnSize,returnColumnSizes, ans); HashTable[nums[i] + 10] = false;//（3） } } } int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){ memset(HashTable, 0 ,sizeof(HashTable)); int **ans = malloc(sizeof(int *) * 720); //最大的数量 (*returnColumnSizes) = malloc(sizeof(int) * 720);//最大的数量 *returnSize = 0; generteP(1,nums, numsSize,returnSize,returnColumnSizes, ans); return ans; }
其实力扣看思想还是舒服的，就是对于OJ可能不适应。
(1). 出口函数 处理结果的返回
(2). 插入hash表
(3). 处理完了 还原状态
2.4 n皇后问题
可以看一下：51. N 皇后，就是国际象棋里面摆放皇后，一共有多少个放法。
如果按照常规思路，是需要枚举n2个位置中选出n个的方案，也就是
，这个数据量非常大。但是n皇后其实不能放同一行同一列，其实能放的就是n的一个全排列。比如例子给的就是2413
void generateP(int index){ if(index == n+1）{ bool flag = true; for(int i = 1;i <= n;++i) for(int j = 1;j <= n;++j) if(abs(i-j) == abs(P[i] - P[j]) flag = false; //不合法 if(flag) count++; return; } for(int x =1; x<= n;x++){ if(hashTable[x] == false){ P[index] = x; hashTable[x] = true; generateP(index+1); hashTable[x] = false; } } }
上面的其实不是原题目的解答，是统计有多少种方案的写法，其实放上来的主要目的是为了告诉大家这里的在最终出现结果的时候进行结果判定是否合法的方式称为暴力法，没想到吧，这就是暴力，是不是日常暴力？？？
更常见的方式是回溯法，就是在执行过程中进行判定，不合法直接返回上一层，更合理。
void generateP(int index){ if(index == n+1）{ count++; //一定合法 return; } for(int x =1; x<= n;x++){ if(hashTable[x] == false){ bool flag = true; for(int pre = 1; pre < index;++pre){ if(abs(index - pre) == abs(x - P[pre]){ flag = false; break; } } if(flag){ //回溯法 P[index] = x; hashTable[x] = true; generateP(index+1); hashTable[x] = false; } } } }
那么接下来就是我们的力扣ac代码：
int P[10],hashTable[11]; const char *s = "........."; void generateP(int index,int n, int* returnSize, int** returnColumnSizes,char *** ans){ if(index == n){ ans [*returnSize] = malloc(sizeof(char *) * n); for(int i = 0;i < n;++i){ ans[*returnSize][i] = malloc(sizeof(char) * (n + 1)); strncpy(ans[*returnSize][i],s,n); ans[*returnSize][i][n] = '\0'; ans[*returnSize][i][P[i]] = 'Q'; } (*returnColumnSizes)[*returnSize] = n; ++(*returnSize); return; } for(int x =0; x< n;x++){ if(hashTable[x] == false){ bool flag = true; for(int pre = 0; pre < index;++pre){ if(abs(index - pre) == abs(x - P[pre])){ flag = false; break; } } if(flag){ //回溯法 P[index] = x; hashTable[x] = true; generateP(index + 1,n,returnSize,returnColumnSizes,ans); hashTable[x] = false; } } } } char *** solveNQueens(int n, int* returnSize, int** returnColumnSizes){ memset(hashTable, 0, sizeof(hashTable)); //全局变量初始化 char *** ans = malloc(sizeof(char **) * 10000);//返回的结果 (*returnColumnSizes) = malloc(sizeof(int) * 10000); (*returnSize) = 0; generateP(0,n,returnSize,returnColumnSizes,ans); return ans; }
Ohhhhhhhhh~,过啦，哈哈哈哈。算是比较难的了。三级指针要命，建议回头用c艹写。。。
推荐专栏
🍭《算法笔记》记录🍭
👻算法笔记刷题👻
🐳课后习题
我写完会放题解，大家写完了可以在评论区打卡哟！题解我放评论区吧，这样不用修改文章。
题解：评论区见，置顶没有就是我没写完0.0，大佬们刷完打个卡
大家加油冲！！！！
