## 编程知识 cdmana.com

### Recursion of data structure and algorithm series (go)

The following complete code can be obtained from here

``https://github.com/Rain-Life/data-struct-by-go/tree/master/recursion/step``

## Understand recursion

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 ！

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

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

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

Let's move on to the theme

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

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

Suppose you're climbing a mountain now , Has climbed to the mountainside , Suppose you want to know how many steps you are on now

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

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

``f(n) = f(n-1) + 1, among f(1)=1``

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

``````func Recursion(int n) int {
if n==1 {
return 1
}

return f(n-1) + 1
}``````

## When is recursion appropriate

As long as a problem can satisfy the following three conditions , Then consider recursion

#### The solution of a problem can be decomposed into solutions of several subproblems

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

#### The sub problem is that the data size is different , The solution must be exactly the same

Or the example above , Ask yourself where you are , The idea is exactly the same as that of the previous step

#### There is a recursive termination condition

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

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

## Write recursive code

Write recursive code , The key is Write recursive formulas 、 Find the recursive termination condition , The rest of the recursive formula into code is simple

#### Example

With Leetcode The above question is an example

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 , 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

After thinking about it, we can know that , actually , You can follow the first step , Divide all walks into two categories

• The first is that the first step is gone 1 A stair
• The second is that the first step is gone 2 A stair

therefore ,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 . It's expressed in terms of the formula ：

``f(n) = f(n-1) + f(n-2)``

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

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

``````n=2
f(2) = f(1) + f(0)``````

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

therefore , The final result of the recursive termination condition is （ You can find a few numbers to verify ）

``f(1)=1,f(2)=2``

With formulas and recursive termination conditions , The code is easy

``````func StepEasy(n int) int {
if n==1 {
return 1
}
if n==2 {
return 2
}

return StepEasy(n-1) + StepEasy(n-2)
}``````

#### analysis

The example above , The human brain can hardly make the whole “ Deliver ” and “ return ” Step by step in the process of thinking clearly

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

《 The beauty of data structure and algorithm 》

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

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

therefore , 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

#### summary

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

## Recursive pit guide

#### 1、 Prevent stack overflow

##### Why recursive code is prone to stack overflow ？

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

If you give too few known numbers , It will cause you to solve the number of unique recursive process is particularly many

stay “ Stack ” 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 . The space of system stack or virtual machine stack is not large . 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

So how to prevent ？

##### How to prevent stack overflow ？

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

Take the upper step as an example

``````var depth = 0
func StepEasy(n int) int {
depth++
if depth > 100 {
panic(" Too many recursions ")
}

if n==1 {
return 1
}
if n==2 {
return 2
}

return StepEasy(n-1) + StepEasy(n-2)
}``````

But it doesn't solve the problem completely , because 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 . 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

#### 2、 Avoid double counting

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 ： 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

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

The problem of going up the stairs , Finally, it can be optimized to this

``````package step

import "fmt"

// 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 ,
// 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 ？

var depth = 0

var mapList = map[int]int{}

func Step(n int) int {
depth++
if depth > 100 {
panic(" Too many recursions ")
}
if n == 1 {
return 1
} else if n==2 {
return 2
}

if mapList[n] != 0 {
return mapList[n]
}
res := Step(n-1)+ Step(n-2)
mapList[n] = res
fmt.Printf("step(%d) = %d", n, mapList[n])
fmt.Println()
return res
}``````

## summary

Except for stack overflow 、 Double counting these two common problems . There are many other problems with recursive code

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) 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

Scroll to Top