编程知识 cdmana.com

Recursion of data structure and algorithm series (go)

{"type":"doc","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The following complete code can be obtained from here "}]},{"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":" Understand recursion "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" I don't know how many times I have been blocked by recursion , Every time I learn recursion , I doubt myself , Is it my brain problem ? I really can't understand it !"}]},{"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":" Understanding recursion before discovery is too rigid and traditional , When looking at recursion, I always follow the execution order of the machine to each level of recursion , And the next layer 、 The next layer 、 The next layer , Until I completely broke down , Their own CPU I didn't finish a complete recursion "}]},{"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":" Our brains always want to follow the machine , Keep going into every layer . In fact, it's possible not to care about every layer , Just assume that the next layer can return correctly , And then I'll do what I have to do , Make sure that the deepest layer of recursive logic is correct , That is, the condition of termination of recursion "}]},{"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":" Because no matter what level of recursion , They all execute the same code , The only difference is the data , Ensure that the recursive logic is correct , The result of each layer is right , Until the termination condition of recursion is satisfied , And then each layer will get the right result "}]},{"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":" Let's move on to the theme "}]},{"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":" Recursion is widely used , so to speak , If you can't fully understand the idea of recursion , Some of the advanced data structures that follow are not legal at all , Or very hard . For example, depth first search 、 Traversal of binary tree and so on "}]},{"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":" Basically most of the books about data structures , When we introduce recursion, we take Fibonacci sequence as an example , In fact, I personally think that although the title is classic , But it didn't help me a lot to understand recursion , Here's a living example to help you understand recursion "}]},{"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":" Suppose you're climbing a mountain now , Has climbed to the mountainside , Suppose you want to know how many steps you are on now "}]},{"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":" Now recursion comes in handy , If you know how many steps are in front of you , I know what level it is , Add one to its series and you'll know what step you're in . But the level in front of you doesn't know what level it is , After all, it's a little far from the bottom of the mountain , There's no way to know . Then keep pushing forward , What step is the first step of the previous step , Until the first step , Then you can send the numbers back one level at a time , Until your front step tells you what level he's on , You'll know what level you're in "}]},{"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":" The whole process is a recursive process , The process of pushing forward is ” Deliver “, When it comes back, it's ” return “. All recursive problems can be represented by recursion , For the example above , To express by formula is to "}]},{"type":"codeblock","attrs":{"lang":"go"},"content":[{"type":"text","text":"f(n) = f(n-1) + 1, among 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) It's the level you want to be at ,f(n-1) It's the first step you've taken ,f(1) We know it's the first step . With formulas, it's easy to write recursive code "}]},{"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":" When is recursion appropriate "}]},{"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":" As long as a problem can satisfy the following three conditions , Then consider recursion "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":4},"content":[{"type":"text","text":" The solution of a problem can be decomposed into solutions of several subproblems "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The subproblem is a smaller problem , For example, the question of which level you are in front of you , Can be broken down into ” Which level is the front one “ Such sub problems "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":4},"content":[{"type":"text","text":" The sub problem is that the data size is different , The solution must be exactly the same "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Or the example above , Ask yourself where you are , The idea is exactly the same as that of the previous step "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":4},"content":[{"type":"text","text":" There is a recursive termination condition "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Break the problem down into subproblems , Subproblems are decomposed into subproblems , Layer by layer , You can't have an infinite loop , And that requires a termination condition "}]},{"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":" Or the example above , The first step is clearly known to be the first step, that is f(1)=1, This is the termination condition for recursion "}]},{"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":" Write recursive code "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Write recursive code , The key is "},{"type":"text","marks":[{"type":"strong"}],"text":" Write recursive formulas 、 Find the recursive termination condition "},{"type":"text","text":", The rest of the recursive formula into code is simple "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":4},"content":[{"type":"text","text":" Example "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" With Leetcode The above question is an example "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"> If there is n A stair , Every time you can cross 1 A step or 2 A stair , Please go here n How many ways to walk a step ?"}]},{"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":" If there is 7 A stair , You can 2,2,2,1 Go up like this , It's fine too 1,2,1,1,2 Go up like this , In short, there are many ways of walking , The next step is to consider how to implement it in code "}]},{"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":" After thinking about it, we can know that , actually , You can follow the first step , Divide all walks into two categories "}]},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The first is that the first step is gone 1 A stair "}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The second is that the first step is gone 2 A stair "}]}]}]},{"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":" therefore ,"},{"type":"text","marks":[{"type":"strong"}],"text":"n The step is equal to go first 1 After the order ,n-1 Step by step plus go first 2 After the order ,n-2 Step by step "},{"type":"text","text":". It's expressed in terms of the formula :"}]},{"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":" With recursive formulas , Now it's almost the termination condition . First , When there is only one step , There must be only one way to go , therefore 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":" however , Is this one recursive termination condition sufficient ? It must not be enough , For example, consider now n=2 and n=3 The situation of , Can we find out by this termination condition "}]},{"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":" If there is only one recursive termination condition f(1)=1, that f(2) It's impossible to solve . So in addition to f(1)=1 This is a recursive termination condition , There will be more f(0)=1, Said go 0 There is a way to move the steps , But it seems that this is not in line with the normal logical thinking . therefore , You can put f(2)=2 As a termination condition , Said go 2 A stair , There are two ways , Take one or two steps "}]},{"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":" therefore , The final result of the recursive termination condition is ( You can find a few numbers to verify )"}]},{"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":" With formulas and recursive termination conditions , The code is easy "}]},{"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":" analysis "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The example above , The human brain can hardly make the whole “ Deliver ” and “ return ” Step by step in the process of thinking clearly "}]},{"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":"> Computers are good at doing repetitive things , So recursion is exactly what it wants . We prefer the way of thinking in a flat way . When we see recursion , We always want to tile recursion , It's going to cycle through the brain , Layer by layer down , And then go back one layer at a time , Trying to figure out how the computer performs every step of the way , So it's easy to get wrapped in "}]},{"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":">《 The beauty of data structure and algorithm 》"}]},{"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":" If a recursive problem wants to try to go through the recursive process through the brain , In fact, it's a mistake in thinking . A lot of times , It's hard to understand , The main reason is that I created this kind of understanding barrier for myself "}]},{"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":" If a question A It can be divided into several subproblems B、C、D, You can assume that the subproblem B、C、D have already been solved , On this basis, think about how to solve the problem A. and , You just need to think about the problem A And sub questions B、C、D The relationship between the two layers can be , There is no need to think about sub problems and sub problems one by one , The relationship between sub sub problems and sub sub problems . Block out recursive details , In this way, it's much easier to understand "}]},{"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":" therefore ,*"},{"type":"text","marks":[{"type":"strong"}],"text":" The key to writing recursive code is , As long as recursion is encountered , Let's abstract it into a recursive formula , You don't have to think about layers of calling relationships , Don't try to use your brain to break down every step of recursion "},{"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":" summary "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"*"},{"type":"text","marks":[{"type":"strong"}],"text":" The key to writing recursive code is to find out how to decompose big problems into small ones , And based on this, write a recursive formula , Then the termination conditions , Finally, the recursive formula and termination conditions are translated into code "},{"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":" Recursive pit guide "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":4},"content":[{"type":"text","text":"1、 Prevent stack overflow "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":5},"content":[{"type":"text","text":" Why recursive code is prone to stack overflow ?"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Share a situation you actually encounter , Before that, the company held a hacker marathon program competition , It's a Sudoku puzzle , The recursive process of Sudoku is used , Here are some known numbers , Solving Sudoku "}]},{"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":" If you give too few known numbers , It will cause you to solve the number of unique recursive process is particularly many "}]},{"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":" stay “"},{"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":" Stack "}]},{"type":"text","text":"” In that article, I shared , Function calls use stacks to hold temporary variables . Every time a function is called , Will encapsulate the temporary variables as stack frames and push them into the memory stack , When the function is finished and returns , Just out of the stack ."},{"type":"text","marks":[{"type":"strong"}],"text":" The space of system stack or virtual machine stack is not large "},{"type":"text","text":". If the data size of recursive solution is large , The call level is very deep , Push all the way into the stack , There's a risk of stack overflow "}]},{"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":" So how to prevent ?"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":5},"content":[{"type":"text","text":" How to prevent stack overflow ?"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" It's also very simple. , You can solve this problem by limiting the maximum depth of recursive calls in your code . Recursive call exceeds a certain depth ( such as 1000) after , We're not going to go on recursion , Direct return error "}]},{"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":" Take the upper step as an example "}]},{"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(\" Too many recursions \")\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":" But it doesn't solve the problem completely , because "},{"type":"text","marks":[{"type":"strong"}],"text":" The maximum allowed recursion depth is related to the amount of stack space left by the current thread , It's impossible to calculate in advance "},{"type":"text","text":". If you calculate in real time , The code is too complex , Will affect the readability of the code . therefore , If the maximum depth is small , such as 10、50, In this way , Otherwise, this method is not very practical "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":4},"content":[{"type":"text","text":"2、 Avoid double counting "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" When using recursion, there will be the problem of repeated calculation , Take the example of taking the steps , hypothesis n=6, Now, recursive decomposition , About the following :"}]},{"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":" From the picture , You can see directly , Want to calculate f(5), It needs to be calculated first f(4) and f(3), And calculation f(4) You need to calculate f(3), therefore ,f(3) It's been calculated many times , This is the problem of double counting "}]},{"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":" To avoid double counting , We can use a data structure ( Like a hash table ) To save the solved f(k). When recursion calls to f(k) when , Let's see if we have solved it . If it is , Then directly take the value from the hash table and return , There is no need to double count , In this way, we can avoid the problems just mentioned "}]},{"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":" The problem of going up the stairs , Finally, it can be optimized to this "}]},{"type":"codeblock","attrs":{"lang":"go"},"content":[{"type":"text","text":"package step\n\nimport \"fmt\"\n\n// If there is n A stair , Every time you can cross 1 A step or 2 A stair , Please go here n How many ways to walk a step ? If there is 7 A stair ,\n// You can 2,2,2,1 Go up like this , It's fine too 1,2,1,1,2 Go up like this , In short, there are many ways of walking , Then how to use programming to find out how many ways to walk in total ?\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(\" Too many recursions \")\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":" summary "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Except for stack overflow 、 Double counting these two common problems . There are many other problems with recursive code "}]},{"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":" In terms of time efficiency , There are many function calls in recursive code , When the number of these function calls is large , It will accumulate into a considerable cost of time . In terms of spatial complexity , Because a recursive call will save the field data in the memory stack once , So when analyzing the spatial complexity of recursive code , This part of the cost needs to be taken into account , For example, we mentioned earlier cinema recursive code , Spatial complexity is not O(1), It is 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":" Please refer to 《 The beauty of data structure and algorithm 》- Recursion , A simple change to the example inside , The code passes go To achieve , The summative text comes from the original text "},{"type":"text","text":"*"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}}]}

版权声明
本文为[InfoQ]所创,转载请带上原文链接,感谢

Scroll to Top