6、递归

一、递归

递归在生活中的使用场景：排队买奶茶，女朋友问前面有几杯在做，你就问了你的前一个人，前一个人买了1杯，然后还问了他的前一个人，那个人买了3杯，然后。。。一直问到排队中的第一个人，得知这个人买的杯数，然后将队伍中的杯数相加，得到前面所有的奶茶杯数

递归在程序中的使用场景：
1、深度优先搜索
2、前中后序二叉树遍历

二、满足递归的3个条件

1、一个问题的解可以分解为几个子问题的解
2、这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
3、存在递归终止条件

三、如何编写递归代码

A、写出递推公式，B、找到终止条件

总结：写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。

四、递归的缺点

1、空间复杂度高
2、有堆栈溢出的风险
3、存在重复计算
解决方法：可以把计算过的数据缓存起来
4、过多的函数调用耗时较多

五、比递归更好的解决方案

用迭代循环来代替(动态规划)

int f(int n) {
  int ret = 1;
  for (int i = 2; i <= n; ++i) {
    ret = ret + 1;
  }
  return ret;
}