递归是我最开始接触编程时候的噩梦，还记得当时被c语言书上的斐波那契数列支配的恐怖。。。
什么是递归
递归是一种很常见且常用的编程技巧，利用递归，我们可以把大问题拆解成若干个小问题，最终由小问题的结果获取得到最终问题的结果。
递归可以视为两个步骤：
第一步是递，将数据拆分传递给函数的过程就是递
第二步是归，拆分后的数据经函数处理后返回结果的过程就是归
以生活场景为例子，相信大家都参加过军训。那军训的时候，都会有报数的环节，那最后一个人想知道自己是多少号时，就得问前面一个人的，前面那个人得问前面的前面的，知道问到第一个人，然后第一个人报数一号，那第二个人得知他前面是一号之后就知道自己是二号了，以此类推，最后一个人就知道自己的号了，总结成方程式就是:
f(1) = 1;
f(n) = f(n-1) +1;
什么时候可以使用递归？
我们如何判断一个问题能否用递归求解呢？
- 可以将一个问题的解分解成几个小问题的解。以上面生活场景为例，最后一个人的号码可以拆解成前面一个人的号码+1
- 待求解的问题和拆解后的小问题，除了数据差异外，求解方式没有任何差异。以上面的生活场景为例，每个小问题的求解方式都是以上一个人的号码+1作为求解方式的。
- 存在递归终止条件。即拆解出来的小问题一定是有尽头的，不能是小问题变成小小问题，小小问题再变成小小小问题，这里一定要有个尽头，以上面的生活场景为例，第一个人就是这个尽头，他不需要再进行拆解，可以直接喊出自己的号码。
如何编写递归
我们知道了什么是递归，也知道了什么问题可以用递归。那么如何编写递归代码呢？
第一步，拆解问题
第二步，列出递归公式
第三步，找出递归终止条件
以leetCode第70题-爬楼梯为例子：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
第一步，拆解问题：
要爬n阶楼梯，因为一次只能走一阶或者两阶，所以我们只要知道你在第n-1阶或者n-2阶时有多少种走法，两者相加就是走到n阶的方法数。
第二步，列出递归公式：
根据第一步，我们知道，我们只需要知道在n-1和n-2位置有多少种走法就行了，所以可以列出递归公式：
f(n) = f(n-1) + f(n-2)
第三步，找出递归终止条件：
我们知道递归不能无休止下去，那拆分出来的子问题最小集是什么呢？答案是一阶或者二阶的时候，即f(1) = 1; f(2) = 2;
这样我们就能写出答案了
使用递归的注意事项
谨防用人脑去递归
为什么初学递归的时候，会觉得递归那么难。可能的原因的就我们把我们的思维也递归下去了，人脑的思维是不太适合递归去想问题的，当你把一个问题拆成一个个小问题，然后再把小问题拆成一个个小小问题，如果人脑要把每个拆分出来的问题想清楚，很容易就混乱了。所以思考递归问题时，关键是需要识别到每个拆分出来的问题和大问题没有区别，只是数据差异，然后只要思考大问题和拆分出来的小问题之间的关系就好了，不需要再递归思考下去。
谨防栈溢出
我们知道临时变量会存储在栈中，如果递归层次过深，很容易导致临时变量不断入栈，最终导致栈溢出，所以在写递归的时候要警惕是否有可能递归过深。
谨防重复计算
上面那个爬楼梯的例子细心的同学可能发现了，存在很多重复计算的过程。以下图为例子
image.png
所以为了防止重复计算，我们可以每个小问题的解存储起来，当遇到相同小问题时，可以直接提取解，而不需要在递归下去
网友评论