数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

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

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

如何理解“递归”?

从我自己学习数据结构和算法的经历来看,我个人觉得,有两个最难理解的知识点,一个是动态规划,另一个就是递归
递归是一种应用非常广泛的算法(或者编程技巧)。之后我们要讲的很多数据结构和算法的编码实现都要用到递归,比如 DFS 深度优先搜索、前中后序二叉树遍历等等。所以,搞懂递归非常重要,否则,后面复杂一些的数据结构和算法学起来就会比较吃力。
不过,别看我说了这么多,递归本身可是一点儿都不“高冷”,咱们生活中就有很多用到递归的例子。
周末你带着女朋友去电影院看电影,女朋友问你,咱们现在坐在第几排啊?电影院里面太黑了,看不清,没法数,现在你怎么办?
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(295)

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

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

    2018-10-12
    8
    1382
  • 刘強
    那个陷入思维误区的说法产生共鸣了,原来总以为自己脑容量不足,看来牛人也一样。
    2018-10-12
    7
    401
  • 一步
    哈哈,在电影院看是第几排,我直接看电影票,直接用索引找到了

    作者回复: 哈哈😄

    2018-10-12
    5
    201
  • 姜威
    总结

    一、什么是递归?

    1.递归是一种非常高效、简洁的编码技巧,一种应用非常广泛的算法,比如DFS深度优先搜索、前中后序二叉树遍历等都是使用递归。
    2.方法或函数调用自身的方式称为递归调用,调用称为递,返回称为归。
    3.基本上,所有的递归问题都可以用递推公式来表示,比如
    f(n) = f(n-1) + 1;
    f(n) = f(n-1) + f(n-2);
    f(n)=n*f(n-1);

    二、为什么使用递归?递归的优缺点?

    1.优点:代码的表达力很强,写起来简洁。
    2.缺点:空间复杂度高、有堆栈溢出风险、存在重复计算、过多的函数调用会耗时较多等问题。

    三、什么样的问题可以用递归解决呢?

    一个问题只要同时满足以下3个条件,就可以用递归来解决:
    1.问题的解可以分解为几个子问题的解。何为子问题?就是数据规模更小的问题。
    2.问题与子问题,除了数据规模不同,求解思路完全一样
    3.存在递归终止条件

    四、如何实现递归?

    1.递归代码编写
    写递归代码的关键就是找到如何将大问题分解为小问题的规律,并且基于此写出递推公式,然后再推敲终止条件,最后将递推公式和终止条件翻译成代码。
    2.递归代码理解
    对于递归代码,若试图想清楚整个递和归的过程,实际上是进入了一个思维误区。
    那该如何理解递归代码呢?如果一个问题A可以分解为若干个子问题B、C、D,你可以假设子问题B、C、D已经解决。而且,你只需要思考问题A与子问题B、C、D两层之间的关系即可,不需要一层层往下思考子问题与子子问题,子子问题与子子子问题之间的关系。屏蔽掉递归细节,这样子理解起来就简单多了。
    因此,理解递归代码,就把它抽象成一个递推公式,不用想一层层的调用关系,不要试图用人脑去分解递归的每个步骤。

    五、递归常见问题及解决方案

    1.警惕堆栈溢出:可以声明一个全局变量来控制递归的深度,从而避免堆栈溢出。
    2.警惕重复计算:通过某种数据结构来保存已经求解过的值,从而避免重复计算。

    六、如何将递归改写为非递归代码?

    笼统的讲,所有的递归代码都可以改写为迭代循环的非递归写法。如何做?抽象出递推公式、初始值和边界条件,然后用迭代循环实现。
    2018-10-12
    5
    136
  • 范柏柏
    希望老师多分享一些经典习题。比如链表那一章课后所说的,掌握这几道题就基本掌握了链表。
    2018-10-12
    1
    124
  • 柠檬C
    递归和数学归纳法非常像,所以可以利用数学归纳法的思路,先验证边界条件,再假设n-1的情况正确,思考n和n-1的关系写出递推公式
    2018-10-12
    3
    73
  • 终于在认知层面得到了提升,递归是什么,在我看来递归就是用栈的数据结构,加上一个简单的逻辑算法实现了业务功能。

    作者回复: 👍

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

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

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

    作者回复: 你理解的也对

    2018-10-12
    3
    32
  • zl
    Debug不行就打日志
    2018-10-12
    30
  • 一步
    说的对的,每次写递归代码,或者看递归代码,都会不自觉的在大脑中复现整个递和归的过程
    2018-10-12
    29
  • L
    解答楼上的问题,数据规模较大的情况用循环,也就是老师讲的非递归代码

    作者回复: 是的 👍

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

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

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

    作者回复: github上艘wangzheng0822

    2018-10-12
    1
    17
  • 风起
    调试递归就像写递归一样,
    不要被每一步的细节所困,
    重点在于确认递推关系与结束条件是否正确,
    用条件断点着重调试最初两步与最终两步即可。
    2018-10-12
    13
  • Monday
    原以为老师会先讲完10个基本的数据结构再讲十种基本的算法。没想到老师会穿插着讲。冒昧的问下老师设计课程的思路。谢谢

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

    2018-10-12
    13
  • 塘泥
    尾递归的问题,想听听老师的讲解
    2018-10-26
    12
  • 落叶飞逝的恋
    关于走楼梯的思路解析:
    1 走到第1级,有1种方法 ,直接走1

    2 走到第2级,有2种方法 (1,1)(2)总共两种走法

    3 走到第3级,有3种方法 (1,1,1)(1,2)(2,1)总共3种走法

    4 走到第4级,有5种方法 (1,1,1,1)(1,1,2)(1,2,1)(2,1,1)(2,2) 总共5种

    5 走到第5级,有8种方法 依次类推

    以此类推,后面的总等于前面两级方法之和,现在使用递归和递推两种方法解决本问题
    2018-11-16
    3
    10
  • AF
    检测环的答案其实老师已经在文章中的一个例子中讲过了,就是用一个数据结构把查询过的元素放到这个数据结构里面,新来的就先查这个数据结构里面有没有,有就返回,没有就放入到这个数据结构里面。
    2018-10-12
    10
  • Smallfly
    ## 界定问题能否用递归解决
    1. 一个问题的解可以分解为几个子问题的解;
    2. 这个问题与分解子问题的求解思路完全相同;
    3. 存在终止条件

    ## 编写递归代码的技巧
    1. 终止条件
    2. 递推公式
    3. 清理现场

    编写递归的关键是思考终止条件,把问题抽象成一个递推公式,并信任它一定能帮我们完成任务,不用想一层层的调用关系,试图用人脑分解递归是反人类的,最多只能想两三层。

    ## 递归的缺点
    递归会利用栈保存临时变量,如果递归过深,会造成栈溢出。解决方案是控制递归的深度。

    递归要警惕重复计算,递归分解的子问题、子子问题可能存在相同的情况,如果都一一计算的话,就会发生重复计算。解决方案是使用散列表来保存结算结果,每次开始计算前检查散列表是否已经有结算结果。

    笼统地讲,递归代码都能用迭代循环来替换。


    免费加入知识星球「极客星球」讨论算法问题。
    2018-10-12
    1
    10
收起评论
99+
返回
顶部