递归

递归的概念分析

递归又分为"递"和“归”，它的大致思路是把方法传递到最低下的最小已知方法，然后在从最小方法一步一步往上求答案归回来。举个例子，假如你去电影院看电影，因为环境太黑你不知道座位在哪一排，你就去问你前一排的人它的座位在第几排，只要知道前一排的座位是第几排就可以知道当前的座位是第几排，而如果前一排的人也不知道他的座位是第几排就会往前问他的前一排，直到问到第一排才给出答案是第一排，这就是递。然后在根据第一排的答案一排一排的往上算，直到算到第n排，这就是归。

image

电影院座位递归

写递归的思路

递归就是将一个问题分解成子问题，直到最后一个子问题有了答案，在往上求解父问题。

首先，不要视图用人脑去逐步分析整个流程，因为有些问题是有几个子问题的解法的，这时用人脑就很难去分析。我们要假设下一个子问题已经知道答案了。

递归的最重要两个问题:第一个父问题跟下面子问题的关系，子问题的终止条件。

例子:假如这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，请问走这 n 个台阶有多少种走法？

思路：我们把N个台阶作为父问题，那它的下一个子问题可能是第n-1个台阶的总解法，也有可能是第n-2个台阶的总解法。现在我们把第n-1和n-2台阶的总解法当作已知，那么对应公式为f(n)=f(n-1)+f(n-2)。我们现在来算子问题的终止条件：有可能是只剩一个台阶，那么f(1)=1,有可能只剩两个台阶，那么f(2)=2。

image

台阶递归解法

使用递归可能带来的问题

1.堆栈溢出

我们知道栈会存储函数的临时变量，递归的调用的次数太多的话，就会造成堆栈的溢出，避免方法就是加个最大执行次数的判断限制。

image

最大执行次数的判断限制

2.重复计算

就像上面的台梯，就有重复计算，可通过键值对保存已经计算好的方法，下次要的时候直接拿来用，避免重复计算

image

f(3)重复计算

image

保存计算结果

3.空间复杂度高

递归改为迭代循环

因为使用递归可能造成的堆栈溢出、重复计算等问题，而改为循环的求解方法，循环的求解思路则是从归开始。

电影院座位号:

image

电影院

台阶方法数：

image

台阶