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

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

  1. 1、本文档共11页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
10|递归:如何用三行代码找到“最终推荐人”? 10| “ ” 递归:如何用三行代码找到 最终推荐人 ? App A B B C 推荐注册返佣金的这个功能我想你应该不陌生吧?现在很多 都有这个功能。这个功能中,用户 推荐用户 来注册,用户 又推荐了用户 来注册。我们可以 C “ ” A B “ ” A A “ ” 说,用户 的 最终推荐人 为用户 ,用户 的 最终推荐人 也为用户 ,而用户 没有 最终推荐人 。 actor_id id referrer_id id 一般来说,我们会通过数据库来记录这种推荐关系。在数据库表中,我们可以记录两行数据,其中 表示用户 , 表示推荐人 。 基于这个背景,我的问题是,给定一个用户ID ,如何查找这个用户的“最终推荐人”?带着这个问题,我们来学习今天的内容,递归(Recursion )! “ ” 如何理解 递归 ? 从我自己学习数据结构和算法的经历来看,我个人觉得,有两个最难理解的知识点,一个是动态规划,另一个就是递归。 DFS 递归是一种应用非常广泛的算法(或者编程技巧)。之后我们要讲的很多数据结构和算法的编码实现都要用到递归,比如 深度优先有哪些信誉好的足球投注网站、前中后序二叉树遍历 等等。所以,搞懂递归非常重要,否则,后面复杂一些的数据结构和算法学起来就会比较吃力。 “ ” 不过,别看我说了这么多,递归本身可是一点儿都不 高冷 ,咱们生活中就有很多用到递归的例子。 周末你带着女朋友去电影院看电影,女朋友问你,咱们现在坐在第几排啊?电影院里面太黑了,看不清,没法数,现在你怎么办? 别忘了你是程序员,这个可难不倒你,递归就开始排上用场了。于是你就问前面一排的人他是第几排,你想只要在他的数字上加一,就知道自己在哪一排了。但 是,前面的人也看不清啊,所以他也问他前面的人。就这样一排一排往前问,直到问到第一排的人,说我在第一排,然后再这样一排一排再把数字传回来。直到 file:///F/temp/geektime/数据结构与算法之美/10递归:如何用三行代码找到“最终推荐人”?.html[2019/1/15 15:35:23] 10|递归:如何用三行代码找到“最终推荐人”? 你前面的人告诉你他在哪一排,于是你就知道答案了。 “ ” “ ” 这就是一个非常标准的递归求解问题的分解过程,去的过程叫 递 ,回来的过程叫 归 。基本上,所有的递归问题都可以用递推公式来表示。刚刚这个生活中的例 子,我们用递推公式将它表示出来就是这样的: f(n)=f(n-1)+1 其中,f(1)=1 f(n)表示你想知道自己在哪一排,f(n-1)表示前面一排所在的排数,f(1)=1表示第一排的人知道自己在第一排。有了这个递推公式,我们就可以很轻松地将它改为递 归代码,如下: int f(int n) { if (n == 1) return 1; return f(n-1) + 1; } 递归需要满足的三个条件 刚刚这个例子是非常典型的递归,那究竟什么样的问题可以用递归来解决呢?我总结了三个条件,只要同时满足以下三个条件,就可以用递归来解决。

文档评论(0)

135****9139 + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档