编程知识 cdmana.com

数据结构与算法系列之递归(GO)

{"type":"doc","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"以下完整代码均可从这里获取"}]},{"type":"codeblock","attrs":{"lang":"go"},"content":[{"type":"text","text":"https://github.com/Rain-Life/data-struct-by-go/tree/master/recursion/step"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"理解递归"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"已经不知道是第几次被递归阻断我学习数据结构的道路了,每次学到递归,我都自我怀疑,是我脑子有问题吗?我是真的学不明白它!"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"发现之前理解递归过于刻板和传统,看递归的时候总是按照机器的执行顺序一直的往每一层递归里边进,不断的下一层、下一层、下一层,直到自己彻底崩溃,自己的CPU也没把一个完整的递归给走完"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"我们的脑子总是想着跟着机器的执行,不停的往每一层里边进。其实完全可以不用关心每一层,只要假定下一层能够正确的返回,然后该怎么走就怎么走,保证最深的一层递归逻辑正确就行,也就是递归终止的条件"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"因为不管是递归的哪一层,他们执行的都是一样的代码,唯一不一样的只是数据而已,保证了递归的逻辑是正确的,每一层的的结果就是正确的,直到递归的终止条件被满足,然后每一层都会得到正确的结果"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"下边进入主题"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"递归应用十分广泛,可以说,如果没法完全的理解递归的思想,后边的一些进阶的数据结构根本没法学,或者非常吃力。比如深度优先搜索、二叉树的遍历等等"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"基本上大多数的关于数据结构的书,在介绍递归的时候都是拿斐波那契数列来举例的,其实我个人觉得虽然题目经典,但对我了解递归帮助不是很大,下边分享一个生活中的示例帮助理解递归"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"假设你现在在爬山,已经爬到了山腰上,假设你现在想知道自己在第多少级台阶上应该怎么办"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"此时递归就派上用场了,那如果你知道你前边一级的台阶是第多少级就行了,知道了它是第多少级,在它的级数上加一就知道你所在的位置是第几级台阶了。但是你前边的这一级也不知道是第几级,毕竟离山底有点远,没法知道。那就继续的往前推,前一级的前一级台阶是第几级台阶,直到第一级台阶,然后就可以一级一级的把数字传回来,直到你的前一级台阶告诉你他在第几级,你就知道了自己在第几级了"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"整个过程就是一个递归的过程,往前推的过程是”递“,回传的时候就是”归“。所有的递归问题都是可以用递归来表示的,对于上边的例子,用公式来表示就是"}]},{"type":"codeblock","attrs":{"lang":"go"},"content":[{"type":"text","text":"f(n) = f(n-1) + 1,其中f(1)=1"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"f(n)是你想自己自己在哪一级,f(n-1)就是你的前一级台阶是第几级,f(1)表示第一级台阶我们知道它是第一级。有了公式写递归代码就很轻松了"}]},{"type":"codeblock","attrs":{"lang":"go"},"content":[{"type":"text","text":"func Recursion(int n) int {\n if n==1 {\n return 1\n }\n \n return f(n-1) + 1\n}"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"什么情况下适合使用递归"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"只要一个问题可以满足下边三个条件,那就可以考虑使用递归"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":4},"content":[{"type":"text","text":"一个问题的解可以分解成几个子问题的解"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"子问题就是规模更小的问题,比如前边的求自己在哪一级台阶的问题,可以分解成”前边一级是哪一级“这样的子问题"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":4},"content":[{"type":"text","text":"子问题除了数据规模不一样,求解思路必须完全一样"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"还是以上边的例子为例,求自己在哪一级台阶,和求解前一级台阶在哪一级的思路是完全一样的"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":4},"content":[{"type":"text","text":"存在递归终止条件"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"把问题分解为子问题,把子问题再分解为子子问题,一层一层分解下去,不能存在无限循环,这就需要有终止条件"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"还是上边的例子,第一级台阶是明确知道是第一级的也就是 f(1)=1,这就是递归的终止条件"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"编写递归代码"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"写递归的代码,最关键的就是"},{"type":"text","marks":[{"type":"strong"}],"text":"写出递归公式、找到递归终止条件"},{"type":"text","text":",剩下的将递归公式转化成代码就简单了"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":4},"content":[{"type":"text","text":"示例"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"以Leetcode上边的一道题为例"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":">假如这里有n个台阶,每次你可以跨1个台阶或者2个台阶,请问走这n个台阶有多少种走法?"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"如果有7个台阶,你可以 2,2,2,1 这样子上去,也可以 1,2,1,1,2 这样子上去,总之走法有很多,下边就是考虑如何通过代码来实现"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"经过思考我们可以知道,实际上,可以根据第一步的走法,把所有的走法分为两类"}]},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"第一类是第一步走了1个台阶"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"第二类是第一步走了2个台阶"}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"所以,"},{"type":"text","marks":[{"type":"strong"}],"text":"n个台阶的走法就等于先走1阶后,n-1个台阶的走法加上先走2阶后,n-2个台阶的走法"},{"type":"text","text":"。用公式表示就是:"}]},{"type":"codeblock","attrs":{"lang":"go"},"content":[{"type":"text","text":"f(n) = f(n-1) + f(n-2)"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"有了递归公式,现在就差终止条件。首先,当只有一个台阶的时候,那肯定就只有一种走法,所以f(1) = 1"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"但是,只有这一个递归终止条件足够吗?肯定是不够的,比如现在考虑n=2和n=3的情况,靠这一个终止条件是否能够求出来"}]},{"type":"codeblock","attrs":{"lang":"go"},"content":[{"type":"text","text":"n=2\nf(2) = f(1) + f(0)"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"如果递归终止条件只有一个f(1)=1,那 f(2)就无法求解了。所以除了f(1)=1 这一个递归终止条件外,还要有f(0)=1,表示走0个台阶有一种走法,不过这样子看起来就不符合正常的逻辑思维了。所以,可以把f(2)=2作为一种终止条件,表示走2个台阶,有两种走法,一步走完或者分两步来走"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"所以,最终得到的递归终止条件就是(可以找几个数字验证一下)"}]},{"type":"codeblock","attrs":{"lang":"go"},"content":[{"type":"text","text":"f(1)=1,f(2)=2"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"有了公式和递归终止条件,代码就很容易了"}]},{"type":"codeblock","attrs":{"lang":"go"},"content":[{"type":"text","text":"func StepEasy(n int) int {\n\tif n==1 {\n\t\treturn 1\n\t}\n\tif n==2 {\n\t\treturn 2\n\t}\n\n\treturn StepEasy(n-1) + StepEasy(n-2)\n}"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":4},"content":[{"type":"text","text":"分析"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"上边的这个例子,人脑几乎没办法把整个“递”和“归”的过程一步一步都想清楚"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":">计算机擅长做重复的事情,所以递归正和它的胃口。而我们人脑更喜欢平铺直叙的思维方式。当我们看到递归时,我们总想把递归平铺展开,脑子里就会循环,一层一层往下调,然后再一层一层返回,试图想搞清楚计算机每一步都是怎么执行的,这样就很容易被绕进去"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":">"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":">《数据结构与算法之美》"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"如果一个递归问题想试图去通过大脑去走一遍递归过程,实际上是进入了一个思维误区。很多时候,理解起来比较吃力,主要原因就是自己给自己制造了这种理解障碍"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"如果一个问题 A 可以分解为若干子问题 B、C、D,你可以假设子问题 B、C、D 已经解决,在此基础上思考如何解决问题 A。而且,你只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可,不需要一层一层往下思考子问题与子子问题,子子问题与子子子问题之间的关系。屏蔽掉递归细节,这样子理解起来就简单多了"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"因此,*"},{"type":"text","marks":[{"type":"strong"}],"text":"编写递归代码的关键是,只要遇到递归,我们就把它抽象成一个递推公式,不用想一层层的调用关系,不要试图用人脑去分解递归的每个步骤"},{"type":"text","text":"*"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":4},"content":[{"type":"text","text":"总结"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"*"},{"type":"text","marks":[{"type":"strong"}],"text":"写递归代码的关键就是找到如何将大问题分解为小问题的规律,并且基于此写出递推公式,然后再推敲终止条件,最后将递推公式和终止条件翻译成代码"},{"type":"text","text":"*"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"递归防坑指南"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":4},"content":[{"type":"text","text":"1、防止堆栈溢出"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":5},"content":[{"type":"text","text":"为什么递归代码容易造成堆栈溢出?"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"分享一个自己实际遇到的一个情况,之前公司举办过一次黑客马拉松的程序比赛,是一道求解数独的题,求解数独的过程就用到了递归,给你一些已知数,求解数独"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"如果给的已知数太少,就会导致你的解数独过程的递归次数特别多"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"在“"},{"type":"link","attrs":{"href":"https://mp.weixin.qq.com/s?_biz=MzU5MjA1MzcyMA==&mid=2247485074&idx=1&sn=83daca776e0efcb08a0c048016aa2ee0&chksm=fe24d225c9535b33f8215db78dfeb58fe7f1b075617139432551a68fb0394874b9cd55f4c48a&token=2027085948&lang=zhCN#rd","title":""},"content":[{"type":"text","text":"栈"}]},{"type":"text","text":"”那一篇文章中有分享到,函数调用会使用栈来保存临时变量。每调用一个函数,都会将临时变量封装为栈帧压入内存栈,等函数执行完成返回时,才出栈。"},{"type":"text","marks":[{"type":"strong"}],"text":"系统栈或者虚拟机栈空间一般都不大"},{"type":"text","text":"。如果递归求解的数据规模很大,调用层次很深,一直压入栈,就会有堆栈溢出的风险"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"那么如何防止呢?"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":5},"content":[{"type":"text","text":"如何预防堆栈溢出?"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"也很简单,可以通过在代码中限制递归调用的最大深度的方式来解决这个问题。递归调用超过一定深度(比如 1000)之后,我们就不继续往下再递归了,直接返回报错"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"以上边的那个台阶为例"}]},{"type":"codeblock","attrs":{"lang":"go"},"content":[{"type":"text","text":"var depth = 0\nfunc StepEasy(n int) int {\n depth++\n\tif depth > 100 {\n\t\tpanic(\"递归次数太多\")\n\t}\n \n\tif n==1 {\n\t\treturn 1\n\t}\n\tif n==2 {\n\t\treturn 2\n\t}\n\n\treturn StepEasy(n-1) + StepEasy(n-2)\n}"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"但这种做法并不能完全解决问题,因为"},{"type":"text","marks":[{"type":"strong"}],"text":"最大允许的递归深度跟当前线程剩余的栈空间大小有关,事先无法计算"},{"type":"text","text":"。如果实时计算,代码过于复杂,就会影响代码的可读性。所以,如果最大深度比较小,比如 10、50,就可以用这种方法,否则这种方法并不是很实用"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":4},"content":[{"type":"text","text":"2、避免重复计算"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"使用递归时还会出现重复计算的问题,还是以走台阶的例子为例,假设n=6,递归分解一下的话,大概如下:"}]},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/3c/3c54b0bd589bc890b81bdc3670cb6568.png","alt":null,"title":"","style":[{"key":"width","value":"50%"},{"key":"bordertype","value":"none"}],"href":"","fromPaste":false,"pastePass":false}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"从图中,可以直观地看到,想要计算 f(5),需要先计算 f(4) 和 f(3),而计算 f(4) 还需要计算 f(3),因此,f(3) 就被计算了很多次,这就是重复计算问题"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"为了避免重复计算,我们可以通过一个数据结构(比如散列表)来保存已经求解过的 f(k)。当递归调用到 f(k) 时,先看下是否已经求解过了。如果是,则直接从散列表中取值返回,不需要重复计算,这样就能避免刚讲的问题了"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"上边那个走台阶的问题,最终就可以优化成这样"}]},{"type":"codeblock","attrs":{"lang":"go"},"content":[{"type":"text","text":"package step\n\nimport \"fmt\"\n\n//假如这里有 n 个台阶,每次你可以跨 1 个台阶或者 2 个台阶,请问走这 n 个台阶有多少种走法?如果有 7 个台阶,\n//你可以 2,2,2,1 这样子上去,也可以 1,2,1,1,2 这样子上去,总之走法有很多,那如何用编程求得总共有多少种走法呢?\n\nvar depth = 0\n\nvar mapList = map[int]int{}\n\nfunc Step(n int) int {\n\tdepth++\n\tif depth > 100 {\n\t\tpanic(\"递归次数太多\")\n\t}\n\tif n == 1 {\n\t\treturn 1\n\t} else if n==2 {\n\t\treturn 2\n\t}\n\n\tif mapList[n] != 0 {\n\t\treturn mapList[n]\n\t}\n\tres := Step(n-1)+ Step(n-2)\n\tmapList[n] = res\n\tfmt.Printf(\"step(%d) = %d\", n, mapList[n])\n\tfmt.Println()\n\treturn res\n}"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"总结"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"除了堆栈溢出、重复计算这两个常见的问题。递归代码还有很多别的问题"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"在时间效率上,递归代码里多了很多函数调用,当这些函数调用的数量较大时,就会积聚成一个可观的时间成本。在空间复杂度上,因为递归调用一次就会在内存栈中保存一次现场数据,所以在分析递归代码空间复杂度时,需要额外考虑这部分的开销,比如我们前面讲到的电影院递归代码,空间复杂度并不是 O(1),而是O(n)"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/60/60253caecc31facc1adc2fff12bf5090.png","alt":null,"title":"","style":[{"key":"width","value":"50%"},{"key":"bordertype","value":"none"}],"href":"","fromPaste":false,"pastePass":false}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"*"},{"type":"text","marks":[{"type":"strong"}],"text":"以上内容参考《数据结构与算法之美》-递归篇,对里边的例子进行了简单的改变,代码通过go来实现,总结性文字皆来自原文"},{"type":"text","text":"*"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}}]}

版权声明
本文为[InfoQ]所创,转载请带上原文链接,感谢
https://xie.infoq.cn/article/294c3fd8d4eb75399d277bd27?utm_source=rss&utm_medium=article

Scroll to Top