数据结构与算法(7)-递归

  1. 1.如何理解递归
  2. 2. 递归的条件
  3. 3. 如何写递归代码
  4. 4. 警惕堆栈溢出
  5. 5. 重复计算问题

1.如何理解递归

    • 去的过程
    • 回来的过程

给我的感觉是先努力去溯源,拿到源数据以后就相当于多了一个信息,然后再依托多了一个的信息,来解决问题。

f(n) = f(n-1) + 1 

2. 递归的条件

  • 一个问题的解可以分解为几个子问题的解
    • 子问题指数据规模更小的解
  • 这个问题与分解之后的子问题,除了数据规模的不同,求解思路完全一样
  • 存在递归终止条件

3. 如何写递归代码

  • 写出递归公式
  • 找到终止条件

E.G

n个台阶,每次可以跨过1个或者2个,问一共多少种走法?

  • 可以划分为子问题,即一共的走法等于我先走一步,剩下的n-1共同的走法和先走两步,剩下的n-1共同的走法的和。就有了一个递归公式:
f(n) = f(n-1) + f(n-2)

终止条件,看最后几个corner case,只有一个台阶,只有两个台阶,然后用3,4来验证一下。

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

不要人为加大难度,遇到递归,抽象成一个递推公式,不再一层层的想其调用关系,不要试图用人脑去分解递归的步骤

分解子问题的时候,当我们将其分解成几个子问题B C D以后,我们要做的是在假设子问题 BCD都已经解决的前提下,思考如何解决问题A。这样子我们就可以思考问题A和子问题B,C,D两层之间的关系就可以了,不需要再一层一层往下思考更深的子问题之间的关系了。屏蔽掉递归的实现细节,我们理解起来就会容易很多了

4. 警惕堆栈溢出

  • 递归容易堆栈溢出
  • 函数调用会使用栈来保存临时变量,每调用一个函数,都会将临时变量封装为栈帧压入内存栈当中。等函数执行完成返回时,才出栈。
  • 系统栈或者虚拟机栈空间都不大,如果递归层很多的话,那么就会有堆栈溢出的风险。
  • 可以在代码中限制递归调用的最大深度来解决这个问题

递归好处是表达能力强,很容易去理顺其想要表达的内容;坏处是空间复杂度会比较高,因为每次递归的时候都需要在内存栈中保存一次现场数据,所以在分析递归代码空间复杂度的时候,是需要额外考虑这部分的开销的。

5. 重复计算问题

子步骤会被计算了很多很多遍,为了避免这种重复计算,可以使用一些数据结构来保存已经求解过得f(k)。当递归调用到f(k)的时候,先看下是否已经求解过了


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 stone2paul@gmail.com

文章标题:数据结构与算法(7)-递归

文章字数:827

本文作者:Leilei Chen

发布时间:2020-02-09, 09:47:26

最后更新:2020-02-09, 09:47:45

原始链接:https://www.llchen60.com/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95-7-%E9%80%92%E5%BD%92/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏