递归作为一种应用非常广泛的算法（或者编程技巧），在很多数据结构和算法的编码实现都会用到递归。例如DFS深度优先搜索、前中后序二叉树遍历等等。
什么情况下可以使用递归？
- 一个问题的解可以分解为若干个子问题的解。
- 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样。
- 存在递归终止条件。
如何编写递归代码？
首先分析问题，确定该问题是否可用递归求解。若可用，则最关键的部分就是写出递推公式了。下面分析一个常见的爬楼梯问题：假如有n个台阶，每次你只能跨1个台阶或两个台阶，问走完这n个台阶，你有多少中走法。
仔细思考后，实际上可以根据第一步的走法把所有的走法分为两类，第一类是第一步走一个台阶，第二类就是第一步走两个台阶。那么第一类的情况下的走法就等于走完一个台阶后剩下的n-1个台阶的走法了，同理，第二类的情况就和走剩下的n-2个台阶的走法一样了。总结起来n个台阶的走法就等于n-1个台阶的走法（第一类）加上n-2个台阶走法（第二类），写出递推公式：f(n) = f(n-1) + f(n-2)。
有了递推公式，递推代码基本就完成了一半了。接下来就是找递推终止条件了，当n=1时只有[{1}]这一种走法，当n=2时有[{1,1},{2}]两种走法。所以递推终止条件就是f(1)=1，f(2)=2。这个时候可以拿n=3，n=4来验证一下。将递推公式和终止条件放在一起就是：f(n) = f(n-1) + f(n-2) 其中f(1)=1，f(2)=2。这不就是斐波那契数列吗，点击查看具体的递归代码。
写递归代码需要注意的问题
警惕堆栈溢出
我们知道函数调用会使用栈来保存临时变量。每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完时返回时才出栈。系统栈或虚拟机栈空间一般都不大，如果递归深度很深，就会有堆栈溢出的风险。针对这种情况，我们可以通过设置最大深度限制值来解决这个问题。当递归深度超过限制值（比如1000）之后，我们就不继续往下递归了，直接返回失败。
警惕重复计算
递归调用过程中经常会出现重复计算某一f(k)的值，为了避免重复计算，我们可以通过一种数据结构（例如散列表）来保存已经求解过的f(k)。
空间复杂度较高
递归调用每进行一次就会在内存栈中保存一次现场数据，所以通常的递归算法的空间复杂度为O(n)。