递归算法

递归定义

递归是一种应用非常广泛的算法（或者编程技巧）。很多数据结构和算法的编码实现都要用到递归，比如：

DFS深度优先搜索
前中后序二叉树遍历

标准的递归求解问题的分解过程：

去的过程叫“递”，
回来的过程叫“归”。

基本上，所有的递归问题都可以用递推公式来表示，如f(n)=f(n-1)+1，其中f(1)=1转换为代码：

func f(n int) int {
 if n == 1 {
  return 1
 }
 return f(n-1) + 1
}

递归需要满足的三个条件

只要同时满足以下三个条件，就可以用递归来解决。

一个问题的解可以分解为几个子问题（数据规模更小的问题）的解
这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
存在递归终止条件：把问题分解为子问题，把子问题再分解为子子问题，一层一层分解下去，不能存在无限循环

编写递归代码

写递归代码最关键的是写出递推公式，找到终止条件，剩下将递推公式转化为代码就很简单了。

假如这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，请问走这 n 个台阶有多少种走法？如果有 7 个台阶，你可以 2，2，2，1 这样子上去，也可以 1，2，1，1，2 这样子上去，总之走法有很多，那如何用编程求得总共有多少种走法呢？

实际上，可以根据第一步的走法把所有走法分为两类：

第一类是第一步走了 1 个台阶
另一类是第一步走了 2 个台阶

所以 n 个台阶的走法就等于先走 1 阶后，n-1 个台阶的走法，加上先走 2 阶后，n-2 个台阶的走法。用公式表示就是：f(n) = f(n-1)+f(n-2)。

有了递推公式，递归代码基本上就完成了一半。

再来看下终止条件，当有一个台阶时，不需要再继续递归，就只有一种走法，所以 f(1)=1。

可以用 n=2，n=3 这样比较小的数试验一下，上述递归终止条件是否满足。

n=2 时，f(2)=f(1)+f(0)。如果递归终止条件只有一个 f(1)=1，那 f(2) 就无法求解了
所以，还要有 f(0)=1，表示走 0 个台阶有一种走法，不过这样子看起来就不符合正常的逻辑思维了
所以，可以把 f(2)=2，作为一种终止条件，表示走 2 个台阶，有两种走法，一步走完或者分两步来走
n=3 时，f(3)=f(2)+f(1)，求解为3，终止条件正确。

综上，递推公式和终止条件并转化为代码：

/*
   递推公式:f(n)=f(n-1)+f(n-2)
   终止条件:f(1)=1,f(2)=2
*/

func f(n int) int {
    if n == 1 {
        return 1
    }
    if n == 2 {
        return 2
    }
    return f(n-1) + f(n-2)
}

写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。

当递归调用只有一个分支，即“一个问题只需要分解为一个子问题”时，很容易能够想清楚“递“和”归”的每一个步骤，所以写起来、理解起来都不难。但是，当一个问题要分解为多个子问题的情况，递归代码就没那么好理解了，人脑几乎没办法把整个“递”和“归”的过程一步一步都想清楚。

计算机擅长做重复的事情，所以递归正和它的胃口，而人脑更喜欢平铺直叙的思维方式。当我们看到递归时，总想把递归平铺展开，脑子里就会循环，一层一层往下调，然后再一层一层返回，试图想搞清楚计算机每一步都是怎么执行的，这样就很容易被绕进去。对于递归代码，这种试图想清楚整个递和归过程的做法，实际上是进入了一个思维误区。很多时候，理解起来比较吃力，主要原因就是自己给自己制造了这种理解障碍。

正确的思维方式应该是：如果一个问题 A 可以分解为若干子问题 B、C、D，可以假设子问题 B、C、D 已经解决，在此基础上思考如何解决问题 A。而且，只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。

因此，编写递归代码的关键是，只要遇到递归，就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

写出递推公式
找到终止条件
翻译成递归代码

递归可能遇到的问题

警惕堆栈溢出

在实际的软件开发中，编写递归代码时，会遇到很多问题，比如堆栈溢出。而堆栈溢出会造成系统性崩溃，后果会非常严重。

回顾“栈”相关内容，函数调用会使用栈来保存临时变量。每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。

以Java为例，将JVM的堆栈大小设置为1KB，在求解较大数据规模时会出现如下堆栈报错Exception in thread "main" java.lang.StackOverflowError。

可以通过在代码中限制递归调用的最大深度的方式来解决这个问题。递归调用超过一定深度（比如 1000）之后，就不继续往下再递归了，直接返回报错。

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

警惕重复计算

使用递归时还会出现重复计算的问题，例如上面求解楼梯走法的问题：

从图中，可以直观地看到：

计算 f(5)，需要先计算 f(4) 和 f(3)
计算 f(4) 还需要计算 f(3)
f(3) 就被计算了很多次

这就是重复计算问题。

为了避免重复计算，可以通过一个数据结构（比如散列表）来保存已经求解过的 f(k)。当递归调用到 f(k) 时，先看下是否已经求解过了。如果是，则直接从散列表中取值返回，不需要重复计算。

将上面求解楼梯走法的代码优化：

var process = make(map[int]int)

func f(n int) int {

    if n == 1 {
        return 1
    }
    if n == 2 {
        return 2
    }
    if process[n-1] != 0 {
        return process[n-1] + f(n-2)
    }
    process[n-1] = f(n - 1)
    return f(n-1) + f(n-2)
}

// 求解30层楼梯，从4ms下降到56us，已经不是一个数量级了

在时间复杂度上，递归多了很多函数调用，当这些函数调用的数量较大时，就会积聚成一个可观的时间成本
在空间复杂度上，递归调用一次就会在内存栈中保存一次现场数据，所以需要额外考虑这部分的开销

递归代码调试

平时调试代码使用 IDE 的单步跟踪功能，像规模比较大、递归层次很深的递归代码，几乎无法使用这种调试方式。

常用的做法：

打印日志发现，递归值
结合条件断点，golang中Delve调试器使用delve debug进入
1. break设置断点
2. condition设置条件

递归改写为非递归

递归操作有点像遍历单链表，需要有指针记录前一个节点，递归代码的非递归实现，也需要有变量记录上一个步骤的结果。

递归有利有弊：

利：是递归代码的表达力很强，写起来非常简洁
弊：是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题

所以，在开发过程中，要根据实际情况来选择是否需要用递归的方式来实现。

func f(n int) int {
    if n == 1 {
        return 1
    }

    if n == 2 {
        return 2
    }

    pre := 2
    prepre := 1
    ret := 0

    for i := 3; i <= n; i++ {
        ret = pre + prepre
        prepre = pre
        pre = ret
    }
    return ret
}

// 求解30层楼梯，在490ns

笼统地讲，所有的递归代码都可以改为这种迭代循环的非递归写法。因为递归本身就是借助栈（系统或者虚拟机本身提供的）来实现的。

如果我们自己在内存堆上实现栈，手动模拟入栈、出栈过程，这样任何递归代码都可以改写成看上去不是递归代码的样子。但是这种思路实际上是将递归改为了“手动”递归，本质并没有变，而且也并没有解决如递归堆栈溢出或重复计算的问题，徒增了实现的复杂度。

递归树

递归代码的时间复杂度分析起来很麻烦。

可以利用递推公式求解，但是，有些情况，用递推公式的话，会涉及非常复杂的数学推导。
除了用递推公式这种比较复杂的分析方法，还可以借助递归树来分析递归算法的时间复杂度。

递归的思想就是，将大问题分解为小问题来求解，然后再将小问题分解为小小问题。这样一层一层地分解，直到问题的数据规模被分解得足够小，不用继续递归分解为止。

如果把这个一层一层的分解过程画成图，其实就是一棵树（递归树）。

如下是一棵斐波那契数列的递归树，节点里的数字表示数据的规模，一个节点的求解可以分解为左右子节点两个问题的求解。

归并排序是一个自上而下的分治过程，每次会将数据规模一分为二。把归并排序画成递归树，如下所示：

每次分解都是一分为二，所以代价很低，把时间上的消耗记作常量1。
比较耗时的是归并操作，也就是把两个子数组合并为大数组。

从图中可以看出，每一层归并操作消耗的时间总和是一样的，跟要排序的数据规模有关。把每一层归并操作消耗的时间记作n。

现在，只需要知道这棵树的高度h，用高度h乘以每一层的时间消耗n，就可以得到总的时间复杂度 $O(n∗h)$ 。

从归并排序的原理和递归树，可以看出来，归并排序递归树是一棵满二叉树。满二叉树的高度大约是 $log_2n$ ，所以，归并排序递归实现的时间复杂度就是 $O(nlogn)$ 。

最后更新于4年前

这有帮助吗？