编程知识 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 :
image.png

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

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

Scroll to Top