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

精选留言(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