递归
概念：
函数直接或间接调用自身的过程
两个关键要素
1.基本情况（递归终止条件）：递归函数中的一个条件，当满足该条件时递归终止，避免无限递归。[直接解决极小规模问题的方法]
2.递归表达式（递归调用）：递归函数中的语句用于解决极小规模的问题，再将子问题的答案合并成为当前问题的答案。
基本结构
返回类型 函数名（参数列表）{
//基本情况（递归终止条件）
 if（满足终止条件）{
  //返回终止条件的结果
 }
//递归表达式
else{
 //将问题分解为规模更小的问题
 //使用递归调用解决问题
 //返回子问题的结果
}
实现：
1.将大问题分解成规模更小的子问题
2.使用递归调用解决每一个子问题
3.通过递归终止条件来结束递归
注意：
1.确保递归一定能到递归出口，避免无限递归导致超时，超内存和运行错误
2.考虑边界条件，有时递归出口不止一个
3.避免不必要的重复计算，尽可能优化递归函数性能
递归和循环的比较
| 递归 | 循环 |
|---|---|
| 1.直观简洁，易于理解和实现 2.适用于问题规模可以通过递归调用不断减小的情况 3.可以处理复杂的数据结构和算法 4.存在栈溢出风险 （栈空间一般只有8MB，所以递归层数不易过深，一般不超过1e6层） |
1.直接控制流程效率更高 2.适用于问题规模没有明显的缩减，或者需要特定的迭代次数 3.适合处理大部分动态规划问题 |
在部分情况下递归和循环可以互相转化。
以上就是递归部分内容了。
爱心 爱心