数据结构与算法之美
王争
前 Google 工程师
283751 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 81 讲
基础篇 (38讲)
数据结构与算法之美
15
15
1.0x
00:00/00:00
登录|注册

10 | 递归:如何用三行代码找到“最终推荐人”?

处理堆栈溢出和脏数据问题
递归查找推荐人
递归代码改写为迭代循环
递归调用的时间和空间开销
使用数据结构保存已求解的结果
限制递归深度
可以通过限制递归深度、使用数据结构、改写为迭代循环等方式解决问题
递归代码存在堆栈溢出、重复计算、时间和空间复杂度等问题
编写递归代码的关键是找到递推公式和终止条件
递归是一种高效、简洁的编码技巧
查找最终推荐人
时间和空间复杂度问题
重复计算问题
堆栈溢出问题
将递推公式和终止条件翻译成代码
找到终止条件
写出递推公式
存在递归终止条件
问题与子问题的求解思路一致
一个问题的解可以分解为几个子问题的解
总结
递归的应用
递归的注意事项
递归的编写方法
递归的定义
递归

该思维导图由 AI 生成,仅供参考

推荐注册返佣金的这个功能我想你应该不陌生吧?现在很多 App 都有这个功能。这个功能中,用户 A 推荐用户 B 来注册,用户 B 又推荐了用户 C 来注册。我们可以说,用户 C 的“最终推荐人”为用户 A,用户 B 的“最终推荐人”也为用户 A,而用户 A 没有“最终推荐人”。
一般来说,我们会通过数据库来记录这种推荐关系。在数据库表中,我们可以记录两行数据,其中 actor_id 表示用户 id,referrer_id 表示推荐人 id。
基于这个背景,我的问题是,给定一个用户 ID,如何查找这个用户的“最终推荐人”? 带着这个问题,我们来学习今天的内容,递归(Recursion)!

如何理解“递归”?

从我自己学习数据结构和算法的经历来看,我个人觉得,有两个最难理解的知识点,一个是动态规划,另一个就是递归
递归是一种应用非常广泛的算法(或者编程技巧)。之后我们要讲的很多数据结构和算法的编码实现都要用到递归,比如 DFS 深度优先搜索、前中后序二叉树遍历等等。所以,搞懂递归非常重要,否则,后面复杂一些的数据结构和算法学起来就会比较吃力。
不过,别看我说了这么多,递归本身可是一点儿都不“高冷”,咱们生活中就有很多用到递归的例子。
周末你带着女朋友去电影院看电影,女朋友问你,咱们现在坐在第几排啊?电影院里面太黑了,看不清,没法数,现在你怎么办?
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

递归算法是一种重要的编程技巧,本文以生活中的例子引出递归的概念,并以推荐注册返佣金功能中的“最终推荐人”查找问题为例,介绍了递归的应用。文章详细讲解了如何理解递归、递归的数学表示和代码实现,以及递归需要满足的三个条件。作者通过生动的例子和简洁的语言,使读者能够快速了解递归算法的基本概念和应用条件。 此外,文章还强调了编写递归代码的关键,警示了递归代码可能导致的堆栈溢出问题,并提出了解决方法。同时,提到了递归代码的重复计算问题,并给出了解决方案。作者还探讨了如何将递归代码改写为非递归代码,以及递归代码的调试方法。 总的来说,本文全面介绍了递归算法的基本概念、应用条件和注意事项,对于初学者和技术人员都具有一定的参考价值。递归算法的优势在于高效简洁,但也存在一些弊端,如堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等问题,因此在编写递归代码时需要注意控制这些副作用。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《数据结构与算法之美》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(518)

  • 最新
  • 精选
  • 博金
    调试递归: 1.打印日志发现,递归值。 2.结合条件断点进行调试。

    作者回复: 答案正确 大家可以把这一条顶上去

    2018-10-12
    27
    2703
  • 哈哈,在电影院看是第几排,我直接看电影票,直接用索引找到了

    作者回复: 哈哈😄

    2018-10-12
    23
    427
  • 终于在认知层面得到了提升,递归是什么,在我看来递归就是用栈的数据结构,加上一个简单的逻辑算法实现了业务功能。

    作者回复: 👍

    2018-10-12
    3
    121
  • mj
    我对台阶问题的理解是:到达n阶只可能来自n-1和n-2,所以f(n)=f(n-1)+f(n-2)

    作者回复: 你理解的也对

    2018-10-12
    12
    96
  • 失火的夏天
    检测环可以构造一个set集合或者散列表(下面都叫散列表吧,为了方便)。每次获取到上层推荐人就去散列表里先查,没有查到的话就加入,如果存在则表示存在环了。当然,每一次查询都是一个自己的散列表,不能共用。不过这样请求量大的话,会不会造成内存空间开辟太多?这里老师能帮忙解答一下吗?

    作者回复: 你这种办法可行的 👍。实际情况 内存也不会耗太多

    2018-10-12
    15
    92
  • Geek_8a2f3f
    王老师,你好!说那个限制递归深度的做法只适合规模比较小的情况,那如果规模大了,怎么限制呢?

    作者回复: 自己模拟一个栈 用非递归代码实现

    2018-10-12
    5
    46
  • L
    解答楼上的问题,数据规模较大的情况用循环,也就是老师讲的非递归代码

    作者回复: 是的 👍

    2018-10-12
    40
  • Monday
    原以为老师会先讲完10个基本的数据结构再讲十种基本的算法。没想到老师会穿插着讲。冒昧的问下老师设计课程的思路。谢谢

    作者回复: 因为后面的内容会用到递归 而递归不依赖后面的内容 拓扑排序了解一下😄

    2018-10-12
    37
  • mobo
    老师好,你的github地址可以发下吗?我在前面的章节没看到

    作者回复: github上艘wangzheng0822

    2018-10-12
    2
    29
  • adapt
    程序员哪来的女朋友😅😂

    作者回复: 那例子就换成男朋友吧😄

    2018-10-12
    24
收起评论
显示
设置
留言
99+
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部