算法之递归

递归是一种应用非常广泛的算法，在很多的数据结构和算法的编码中都会用到，理解递归是非常重要的。

递归在平时的生活中也是非常常用的，当你排队的时候需要知道自己排在第几个位置，而前面的人又比较多，你不能自己数出来，就可以询问你前一个人他的位置，在他的位置基础上加一便是你的位置，那如果他也不知道他的位置呢，就可以用同样的方法，继续向前询问，直到第一个人，第一个人就不用往前问了，他直到自己是第一个，这个过程就是一个递归的过程。

去问的时候叫做“递”，返回来的时候叫做“归”，假设自己是第n排，求自己位置的函数为f(n)，f(n-1)就是前一个人的位置，我们的位置就是f(n-1)+1，同样前一个人的位置也可以用这个公式来计算， 直到第一个人f(1)=1，这一整套流程便是递归的实际利用，编写成代码如下

在编写递归代码的时候，有两点必要的条件：

•一个问题可以分解为多个结构相同，规模不同的子问题。•存在终止条件。

如果结构不同，那就不能构造递归了；如果不存在终止条件的话，将会无限循环，看上面的那个例子，它的终止条件就是执行到第一个人的时候，开始往后返回。

递归就这样完成了，上面这个例子是只有一个递归调用的分支，还是比较好理解的，如果有多个递归分支的话，单纯靠人脑是很难理解清楚的，计算机比较适合做重复的工作，我们如果一环一环往递归里走的话，很快就迷糊了，唯一的方法就是自己屏蔽掉其中细节，只把握好第一个递归公式的构造和终止条件的判断，就能更好的理解清楚递归了。

假如有n阶台阶，可以每次走一个台阶或两个台阶，请问走完n阶楼梯有多少种走法？

•如果有一层台阶，(1)，有一种.•如果有两层台阶，(1,1)、(2)，有两种•如果有三层台阶，(1,1,1)、(1,2)、(2,1)，有三种•如果有四层台阶 ，(1,1,1,1)、(1,1,2)、(1,2,1)、(2,1,1)、(2,2)，有五种•如果有五层台阶 ，(1,1,1,1,1)、(1,1,1,2)、(1,1,2,1)、(1,2,1,1)、(2,1,1,1)、(1,2,2)、(2,1,2)、(2,2,1)，有八种•以此类推

举几个例子，就可以很明显的发现，从第三层开始，每一层都是前两层的次数相加，所以我们就可以得到公式f(n) = f(n-1)+f(n-2) ，通过举例子是最容易理解的一个方式，实际上去理解的方法有很多种，可以自己去尝试，你可以用递归的想法去一层层跑一下，就会发现整体的困难程度是非常大的。

所以将其转换为代码就如下图所示

在写递归代码的时候，还需要注意两个问题：

•警惕堆栈溢出•警惕重复计算

先说堆栈溢出，在函数调用时，会使用栈来保存临时变量，每进行一次函数调用，就会将临时变量封装后压入内存栈，这个栈的大小是由系统来决定的，如果递归太深，压入栈中的数据是非常多的，就会有堆栈溢出的风险；解决办法就是在递归函数中加入一个判断条件，来判断递归的深度，如果达到了某一个值，就直接返回报错。

另一个就是重复计算，当我们在计算f(5)的时候会计算f(4)和f(3)，在计算f(4)的时候还需要计算f(3)，f(3)就被重复计算了，为了避免重复计算，可以通过数据结构来记录已经计算过的值，在计算前先进行判断，如果计算过就直接将值返回。

为了避免这些情况，也可以将递归代码改为迭代循环的非递归方式，就是使用循环的方式来进行处理。

参考文档

极客时间-数据结构与算法之美