前言递归是一个很重要的概念，在面试中也很流行。因为它不仅可以考查一个程序员的算法功底，还可以很好地考查对时空复杂度的理解和分析。本文只讲一个题，也是几乎所有算法书上关于递归的第一道题，但我尽量讲一下，在这里分享四个不同的角度，让大家有不同的收获。时空复杂度详解识别并简化递归过程中的重复操作披着羊皮的狼炫技帮我找到了第一份工作算法思路大家都知道调用自己的方法是递归的，没错，但这只是对递归的最肤浅的理解。那么递归的本质是什么？答：递归的本质就是能够把一个大问题分解成更小的问题，然后我们就可以用小问题的解来构造大问题的解。你如何得到小问题的解决方案？答：它是用较小问题的解构造的。太小时就是零问题，也就是basecase。然后总结一下递归的三个步骤：Basecase：是递归的零问题，也是递归的结束。当到达最小的问题时，直接给出结果就可以了，不需要再进一步，否则就是死循环；拆解：每一层的问题都比上一层的问题小，问题的大小可以不断缩小，从大到小到basecase；组合：要得到小问题的解，你需要知道如何构造它对大问题的解。所以对于每一道递归题，我们都是按照这三个步骤来分析的。这三个问题弄清楚了，代码就好写了。斐波那契数列这个话题虽然老生常谈，但相信我在这里分享的内容一定会给大家带来其他的收获。题目描述斐波那契数列是意大利数学家。他可以自由地研究兔子的繁殖过程。经过研究，他发现可以写成这样的数列：1、1、2、3、5、8、13、21……也就是说，每个数都等于它前面两个数的和。然后给你第n个数，问F(n)是多少。用数学公式表达分析很简单：代码也很简单，用我们刚才总结的三个步骤：basecase:f(0)=0,f(1)=1.Decomposition:f(n-1)、f(n-2)组合：f(n)=f(n-1)+f(n-2)然后写出：classSolution{publicintfib(intN){if(N==0){return0;}elseif(N==1){return1;}returnfib(N-1)+fib(N-2);}}但是这个解法Leetcode给出的速度体验只比15%的答案快，因为它的时间复杂度实在是太高了！过程分析。这是我要分享的第一点，如何分析递归过程。首先，我们绘制递归树。比如我们画出F(5)的递归树：实际的执行路线是怎样的？首先，沿着最左边的一行一直走到最后：F(5)→F(4)→F(3)→F(2)→F(1)，好了，终于有一个可以返回F的basecase了(1)=1，再回到F(2)层，再往下走，就是F(0)，又再次触底，回到F(2)，得到F(2)的结果)=1+0=1，把这个结果返回给F(3)，再去F(1)，得到结果再返回F(3)，得到F(3)=left+right=2，然后返回结果...这个方法本质上是我们计算机的冯·诺依曼系统创造的，目前一个CPU和一个核在某一时刻只能执行一条指令，所以F(3)和F(4)不能一起执行，必须先执行F(4)（这段代码把fib(N-1)放在前面），再执行F(3)。我们在IDE中调试可以看到栈中的情况：这里确实是最左边的行先走，一共有5层，然后逐层走。回来。时间复杂度分析如何评价一个算法的好坏？很多问题都有多种解决方案，毕竟条条大路通罗马。但是如何评价每种方法的优劣，我们一般用大O表达式来衡量时间和空间复杂度。时间复杂度：随着自变量数量的增加，算法所需的时间也会增加。这里的大O代表算法在最坏情况下的性能。这是我们最关心的。否则春节期间抢票系统将无法hold。你跟我说这个算法优秀？当然，还有其他时间和空间的度量方式，比如Theta：描述紧束缚Omega(n)：这个描述最好的情况，最好的情况，没有意义。这也给了我们一些启发。意义;面试衡量的是你在最坏情况下的水平；别说面试没有表现出你的真实水平，伤人的是那才是我们的真实水平。那么对于这道题，时间复杂度是多少呢？答：因为我们每个节点都经过了一次，所以总时间就是所有节点时间的总和。这里，我们对每个节点做的是加法和求和，是一个O(1)的操作，而且每个节点的时间都是一样的，所以：总时间=节点数*每个节点时间时间就成了一个数学问题求节点个数：当N=5时，顶层有1个节点，第二层有2个节点，第三层有4个节点，第四层有8个节点，第五层有8个节点16,如果是满的,想象成一棵大树:)不用管这里没填的地方,肯定有几个节点的区别,但是我们刚才说的大O表达式的时间复杂度Passed,要找的是最坏的情况。那么节点总数为：1+2+4+8+16这是一个几何数列的和。当然，你可以用数学公式来计算，但还是有一个小技巧可以帮助你快速计算：其实前面每一层的节点总数不会超过最后一层的节点数，总节点数最多为最后一层节点数*2，然后O的时间复杂度中的常数项无所谓，所以总时间复杂度为：最后一层节点数：2^n不明白？不要慌，去B站/youtube看我的视频讲解，搜索“田小七”即可。空间复杂度分析一般书上写的空间复杂度指的是：算法运行过程中需要的所有内存空间，但是在公司里比较常用，面试的时候也会问到。辅助空间复杂度：运行算法时需要占用的额外空间。举个例子说明一下区别：比如结果允许你输出一个长度为n的数组，那么这个O(n)的空间是不计入算法的空间复杂度的，因为这个空间无法转义，它不取决于你的算法。如何分析空间复杂度？刚才我们讲了冯诺依曼系统，从图中很容易看出，最左边的路由在栈中占用的空间最多，一直在压栈，即从5到4到3到2，直到按下1直到基本情况返回。每个节点占用的空间复杂度为O(1)，所以总的空间复杂度为O(n)。我在上面👆视频里也有提到，不明白的请自己看视频~然后我们想到了优化算法，为什么这么简单的运算时间复杂度是指数级的？为什么时间这么复杂？很大。不难看出，这个RecursionTree中重复的计算太多了。比如这里一个F(2)计算了3次，F(3)计算了2次，每次都得重新计算。这不就是熊掰棍子吗？真的是辛酸的眼泪。找到原因后，为了解决这种重复计算，计算机使用的方法其实和我们人类是一样的：做笔记。很多职业，比如医生、律师，还有我们的工程师，为什么越老的经历越值钱？因为我们看的多，积累的多，下次再遇到类似的问题，也能很快给出解决方案，即使一时解决不了，也避免了一些盲目的试错。我们会从过去的高度继续改进，而不是每次都从头开始。回到优化算法，计算机是如何做笔记的？我们要求F(n)，无非就是记录下F(0)~F(n-1)的值，然后选择合适的数据结构来存储即可。那么这里就很明显了，可以用之前说的HashMap（没看过的可以点击阅读）或者用数组存储：Index012345F(n)011235就这样有了这个cheatsheet，我们就可以从前到后得到结果，这样每个点只计算一次，而且可以用for循环来写，代码也很简单。classSolution{publicintfib(intN){if(N==0){return0;}if(N==1){return1;}int[]notes=newint[N+1];notes[0]=0;notes[1]=1;for(inti=2;i<=N;i++){notes[i]=notes[i-1]+notes[i-2];}returnnotes[N];}}这个速度是100%~不过我们可以看出空间上应该还有优化的余地。那么仔细想一想，我们做笔记的时候真的需要记录那么多笔记吗？从幼儿园到小学到初中到高中，我们需要记笔记吗？实际上每一项的计算只依赖于前面两项，所以只用保留那两项即可。那么我们可以使用长度为2的数组来计算，或者只使用2个变量。更新代码：classSolution{publicintfib(intN){inta=0;intb=1;if(N==0){returna;}if(N==1){returnb;}for(inti=2;i<=N;i++){inttmp=a+b;a=b;b=tmp;}returnb;}}这样，我们将空间复杂度优化为O(1)，时间复杂度与使用数组记录一样。).这种方法其实就是动态规划，写的代码也很简单。然后再对比一下Recursion和DP：Recursion是从大到小，逐层分解，直到basecase无法分解，然后组合返回；DP是从小到大，做好笔记，精益求精。即Recursion+Cache=DP如何记录这个笔记，如何高效的做笔记，这就是DP的难点。有人说DP是用空间换时间，我不这么认为。这个问题就是一个很好的例子。用递归求解问题的时候，我们可以看到栈上的空间是O(n)，但是用DP我们可以把空间优化到O(1)，DP可以实现时间和空间的双重优化。事实上，斐波那契数列在现实生活中有很多应用。比如我们公司和很多大公司，每个任务都需要打分。1分表示需要1天左右的时间完成，然后分数只有1、2、3、5、8。（如果有超过8分的任务，需要分解为8分以内，让大家在两周内完成。)因为任务是无穷无尽的，每个人的时间都是有限的，所以每次小组开会的时候，挑出最重要的任务给大家做，然后每个人根据可用的天数来接。任务。披着羊皮的狼，可能有的同学会想，这道题这么简单，都2020年了，还会面试吗？答：真的。只是不能这么直白的给你。比如大家熟知的爬楼梯问题：一个N步的楼梯一次可以走一层或两层楼，问一共有多少种方式。这道题可以这样想：站在当前位置，只能从上一层或者前两层来，所以f(n)=f(n-1)+f(n-2)。真正被问到的时候，我还在写python。为了大显身手，我还用了lambda函数的递归写法：f=lambdan:1ifnin(1,2)elsef(n-1)+f(n-2)时间复杂度太高，所以我写了一个for循环版本deffib(n)a,b=1,1foriinrange(n-1):a,b=b,a+breturna然后写了一个缓存方法：defcache(f):memo={}defhelper(x):ifxnotinmemo:memo[x]=f(x)returnmemo[x]returnhelper@cachedeffibR(n):ifn==1orn==2:return1returnfibR(n-1)+fibR(n-2)也和面试官关于尾递归：tailrecursion尾递归：递归语句是整个方法的最后一句。那么这有什么特别之处呢？尾递归的特点是我们很容易将其转化为迭代的写法。当然，有些聪明的编译器会自动帮我们做（不是说显式转换，而是在运行的时候是迭代运行的，实际消耗的空间是O(1)），那为什么呢？因为返回的时候不需要回溯，而这里的递归是最后一步，不需要返回下一层。deffib(n,a=0,b=1):ifn==0:returnaifn==1:returnbreturnfib(n-1,b,a+b)最后拿出我的王牌：lambda和reducefibRe=lambdan：reduce(lambdax,n:[x[1],x[0]+x[1]],range(n),[0,1])看到面试官满意的表情后，开始继续深入聊……所以，不要以为这很简单。同一个问题可以有七八种解法。分析每种方法的优缺点，把它扩展到你可以扩展的地方，展现你扎实的基本功。这次面试其实就是给你个炫耀的机会，好骗过面试官~lol
