详解「递归」正确的打开方式

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

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

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

算法思路

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

那么递归的实质是什么?

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

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

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

 

的三个步骤：

Base case：就是递归的零号问题，也是递归的终点，走到最小的那个问题，能够直接给出结果，不必再往下走了，否则，就会成死循环;

拆解：每一层的问题都要比上一层的小，不断缩小问题的 size，才能从大到小到 base case;

组合：得到了小问题的解，还要知道如何才能构造出大问题的解。

所以每道递归题，我们按照这三个步骤来分析，把这三个问题搞清楚，代码就很容易写了。

斐波那契数列

这题虽是老生常谈了，但相信我这里分享的一定会让你有其他收获。

题目描述

斐波那契数列是一位意大利的数

（编辑：淮安站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!