递归算法编程技巧总结 第1篇

刚刚这个例子是非常典型的递归，那究竟什么样的问题可以用递归来解决呢？这里总结了三个条件，只要同时满足以下三个条件，就可以用递归来解决。

何为子问题？子问题就是数据规模更小的问题。比如之前所讲的例子，对于“自己在哪一排”的问题，可以分解为“前一排的人在哪一排”这样一个子问题。

比如电影院的例子，你求解“自己在哪一排”的思路，和前面一排人求解“自己在哪一排”的思路，是一模一样的。

把问题分解为子问题，把子问题再分解为子子问题，一层一层的分解下去，不能存在无限循环，这就需要有终止条件。在电影院例子当中，第一排的人不需要再继续询问任何人，就知道自己在哪一排，也就是f(1)=1，这就是递归的终止条件。

递归算法编程技巧总结 第2篇

在之前“栈”那篇博客当中，我们了解到了函数调用栈的概念，我们知道函数调用会使用栈来保存临时变量。每调用一个函数，都将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。系统栈或者虚拟机栈空间的大小一般都不大。如果递归求解的数据规模很大，导致调用层次很深，一直将栈帧入栈，就会有堆栈溢出的风险。

当堆栈溢出时便会出现如下堆栈报错信息：

那么，应该如何避免出现堆栈溢出呢？

我们可以通过在代码中限制递归调用的最大深度的方式来解决这个问题。递归调用超过一定深度(比如1000)之后，我们就不继续往下再递归了，直接返回错误。还是电影院那个例子，我们可以改造成下面这个样子，就可以避免堆栈溢出了。

但是这种做法并不能完全解决问题，因为最大允许的递归深度跟当前线程剩余的栈空间大小有关，事先无法计算。如果实时计算，代码过于复杂，就会影响代码的可读性。所以，如果最大深度比较小，比如10、50，就可以用这种方法，否则这种方法并不是很实用。

另外我们可以通过将递归函数当中所需的数据，在不影响代码执行的条件下定义为全局静态变量，这样就减少了函数调用时，压入堆栈当中栈帧的大小了，从而减轻了内存的负担。

递归算法编程技巧总结 第3篇

之前我们了解到，我们将问题转化为递归的形式解决时，不必考虑具体子问题的执行细节，只需考虑递归公式和终止条件即可，这就是递归的优点：递归代码的表达力极强，写起来也非常简洁；但是递归也存在空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。所以在开发过程中，我们要根据实际情况来选择是否需要用递归的方式来实现。

接下来我们将电影院例子的递归代码改写为非递归代码：

同样将第二个上楼梯的例子也改写为非递归的实现方式：

那是不是所有的递归代码都可以改为这种迭代循环的非递归写法呢？笼统的讲，是的。因为递归本身就是借助栈来实现的，只不过我们使用的栈是系统或者虚拟机本身提供的，我们没有感知罢了。如果我们自己在内存堆上实现栈，手动模拟入栈、出栈过程，这样任何递归代码都可以改写成看上去不是递归代码的样子。

但是这种思路实际上是讲递归改为了“手动”递归，本质没有改变，而且也没有解决前面讲到的某些问题，徒增了实现的复杂度。