递归的实质是能够把一个大问题分解第一

清溪算法 2020-06-21

前言

递归,是一个非常重要的概念,也是面试中非常喜欢考的。因为它不但能考察一个程序员的算法功底,还能很好的考察对时间空间复杂度的理解和分析。

本文只讲一题,也是几乎所有算法书讲递归的第一题,但力争讲出花来,在这里分享四点不一样的角度,让你有不同的收获。

  • 时空复杂度的详细分析
  • 识别并简化递归过程中的重复运算
  • 披上羊皮的狼
  • 适当炫技助我拿到第一份工作

算法思路

大家都知道,一个方法自己调用自己就是递归,没错,但这只是理解递归的最表层的理解。

那么递归的实质是什么?

答:递归的实质是能够把一个大问题分解成比它小点的问题,然后我们拿到了小问题的解,就可以用小问题的解去构造大问题的解。

那小问题的解是如何得到的?

答:用再小一号的问题的解构造出来的,小到不能再小的时候就是到了零号问题的时候,也就是 base case 了。

相关推荐