Violin's Blog
0%

递归

发表于 分类于 本文字数： 1.4k 阅读时长 ≈ 4 分钟

今天来学习递归。

如何理解“递归”

数据结构和算法中两个最难理解的知识点，一个是动态规划，另一个是递归。

递归是一种应用非常广泛的算法(或者编程技巧)。比如，合并两个有序链表、斐波那契数列等等。

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

递归需要满足的三个条件

  1. 一个问题的解可以分解为几个子问题的解。子问题就是数据规模更小的问题。
  2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样。
  3. 存在递归终止条件

如何编写递归代码

写递归代码最关键的是写出递归公式，找到终止条件。

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

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

递归代码要警惕堆栈溢出

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

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

将递归代码改为循环处理以避免堆栈溢出。

递归代码要警惕重复计算

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

将递归代码改写为非递归代码

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

f(x)=f(x-1)+1改写为非递归代码

1
2
3
4
5
6
def f(n):
    result = 1

    for i in range(2, n+1):
        result = result + 1
    return result

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

解答开篇

给定一个用户ID，如何查找这个用户的“最终推荐人”。伪代码如下，

1
2
3
4
5
long findRootReferrerId(long actorId) {
  Long referrerId = select referrer_id from [table] where actor_id = actorId;
  if (referrerId == null) return actorId;
  return findRootReferrerId(referrerId);
}

存在的问题：

  1. 递归很深，存在堆栈溢出的风险(限制递归次数)
  2. 如果数据库里存在脏数据，还需要处理由此产生的无限递归问题，如何检测环？(限制递归次数、快慢指针检测环)

课后思考

对于递归代码，有什么好的调试方法？(答案来自评论区)

  • 打印日志发现，递归值
  • 结合条件断点进行调试
您的支持将鼓励我继续创作！