preface
Recursion is a very important concept and a very popular one to ask in an interview. Because it can not only examine a programmer’s algorithm, but also a good understanding and analysis of time and space complexity.
This article only talks about one problem, is also the first problem that almost all algorithm books talk about recursion, but strive to speak flower, here share four different angles, let you have different harvest.
- Detailed analysis of space-time complexity
- Identify and simplify repeated operations in recursion
- A Wolf in sheep’s clothing
- A little showmanship helped me get my first job
Algorithm ideas
You all know that a method that calls itself is recursion, yes, but that’s just the surface of understanding recursion.
So what is the essence of recursion?
A: The essence of recursion is to be able to decompose a big problem into smaller problems. Then we have the solution of the small problem and we can use the solution of the small problem to construct the solution of the big problem.
How did you get the solution to the little problem?
A: It is constructed from the solution of a smaller problem. When it is as small as possible, it is the time for the zero problem, which is the base case.
So to summarize the three steps of recursion:
Base case: it is the zero problem of recursion, which is also the end of recursion. If you go to the smallest problem, you can give the result directly. There is no need to go further, otherwise, it will become an infinite loop.
Dismantling: The problems of each layer should be smaller than those of the previous layer, and the size of the problem should be continuously reduced to base case from large to small;
Combination: you get the solution of a small problem, but you also know how to construct the solution of a big problem.
So for every recursion, we go through these three steps, and we figure out these three problems, and the code is easy to write.
Fibonacci numbers
It’s a cliche, but I’m sure you’ll learn something else.
Topic describes
The Fibonacci sequence was an Italian mathematician who spent his spare time studying the reproduction of rabbits and discovered that it could be written as follows: 1,1,2,3,5,8,13,21… So each number is equal to the sum of its first two numbers. So to give you the NTH number, what is F of n.
parsing
It’s easy to write this mathematically:
The code is simple, using the three steps we just summarized:
- base case: f(0) = 0, f(1) = 1.
- Decomposition: F (n-1), F (n-2)
- Combination: F (n) = F (n-1) + F (n-2)
So write it as:
class Solution {
public int fib(int N) {
if (N == 0) {
return 0;
} else if (N == 1) {
return 1;
}
return fib(N-1) + fib(N-2);
}
}
Copy the codeBut Leetcode gives us a speed experience that is only 15% faster, because the time complexity is too high!
Process analysis
So that’s the first thing I want to share, how to analyze recursion.
First let’s draw the Recursion Tree. For example, let’s draw the Recursion Tree for F(5) :
What is the actual implementation route?
First, follow the leftmost line all the way to the end: F(5) → F(4) → F(3) → F(2) → F(1) → F(2) → F(1) F(2) =1 +0 =1, return the result to F(3), return the result to F(1), return the result to F(3), return the result to F(3) = left + right = 2, return the result back…
This method is essentially created by the von Neumann system of our computer. Currently, one CPU and one core can only execute one instruction at a time, so F(3) and F(4) cannot be carried out together. It must be executed first (fib(n-1) is put in front of this code), and then F(3) is executed.
We debug in the IDE to see what’s going on in the stack: this is actually the leftmost line that goes first, there are 5 levels, and then one level up and back up.
If you don’t understand, you can go to YouTube or B station to watch the video
Time complexity analysis
How do you evaluate an algorithm?
There are many solutions to many problems. After all, all roads lead to Rome. However, to evaluate the merits of each method, we generally use large O expressions to measure the time and space complexity.
Time complexity: The increase in time required as the independent variable increases.
The big O here represents the performance of an algorithm in the worst case, which is what we care most, otherwise the system will not be able to hold when snatching tickets during the Spring Festival Travel rush. Did you tell me that this algorithm is excellent?
There are other ways of measuring time and space, for example
Theta describes tight bound Omega(n): This describes best case, which doesn’t make any sense
It also gives us a little bit of inspiration, don’t say how well you perform on a regular basis, it doesn’t matter; The interview measures your level in a worst case; Don’t say that the interview is not at your best, but it is at our best.
So what is the time complexity for this problem?
A: Because we went through each node, the total time is the sum of all nodes.
Here, what we are doing on each node is summing, which is O(1) operation, and the time is the same on each node, so:
Total time = Number of nodes x time of each node
That becomes the math of finding the number of nodes:
At N = 5,
The top layer has 1 node, the second layer has 2 nodes, the third layer has 4 nodes, the fourth layer has 8 nodes, and the fifth layer has 16 nodes. If it is filled, imagine it as a big tree 🙂
Don’t worry about the empty space here, there will be a difference of several nodes, but the time complexity of big O is the worst case we just talked about.
So the total number of nodes is: 1 + 2 + 4 + 8 + 16
This is the sum of a geometric sequence, and of course you can do it mathematically, but here’s a little trick to help you do it quickly:
In fact, the total number of nodes in each previous layer cannot exceed the number of nodes in the last layer. The total number of nodes is at most the number of nodes in the last layer * 2, and the constant term does not matter in the time complexity of big O, so the total time complexity is:
Number of nodes in the last layer: 2^n
Spatial complexity analysis
Generally, space complexity in books refers to:
All the memory space that the algorithm needs to occupy while it is running
The Auxiliary space is full of complexity, too.
The extra space required to run the algorithm.
To illustrate the difference: if the result tells you to output an array of length N, then the O(n) space does not count in the algorithm’s space complexity, because the space is inescapable, not dependent on your algorithm.
What about spatial complexity?
We just talked about the von Neumann system, and it’s easy to see from the diagram, that it’s the one on the left that takes up the most space on the stack, and it keeps pushing, that is, from 5 to 4 to 3 to 2 until it gets to 1, and then it gets back to the base case, and the space complexity of each node is O(1), So it adds up to order n.
I also mentioned in the video at 👆 above, if you don’t understand, look up the video oh ~
Optimization algorithm
So we thought, why does something so simple need to be exponentially time complex? What makes time so big?
It’s not hard to see. There’s a lot of double counting in this Recursion Tree.
For example, if F(2) has been calculated three times, and F(3) has been calculated twice, each time it has to be recalculated, it is like a dog breaking a bone, it is really a handful of bitter tears.
After finding out why, computers tackle this double-counting in the same way that we do: by taking notes.
For many professions, like doctors and lawyers, and for us engineers, why is experience worth more with age? Because we have seen more and accumulated more, the next time we encounter similar problems, we can quickly provide solutions, even if it can not be solved for a while, also avoid some blind trial and error, we will continue to make progress at the height of the past, rather than starting from zero every time.
Back to the optimization algorithm, how does a computer take notes?
We want to find F(n), is nothing more than to record the value of F(0) ~ F(n-1), then select a suitable data structure to store it.
So here’s the obvious, use an array to store:
| Index | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| F(n) | 0 | 1 | 1 | 2 | 3 | 5 |
So with this Cheat sheet, we can get the result from front to back, so that each point can be calculated only once, using a for loop to write out, the code is very simple.
class Solution {
public int fib(int N) {
if (N == 0) {
return 0;
}
if (N== 1) {
return 1;
}
int[] notes = new int[N+1];
notes[0] = 0;
notes[1] = 1;
for(int i = 2; i <= N; i++) {
notes[i] = notes[i-1] + notes[i-2];
}
return notes[N];
}
}
Copy the codeThis speed is 100% ~
But as we can see, there should be room for optimization.
When you think about it, do we actually need to take notes that much? Do YOU need to keep your notes from kindergarten through elementary school to middle school through high school?
So each term really only depends on the two terms in front of it, so I’m just going to keep those two.
So we could do it with an array of length 2, or we could do it with just 2 variables.
Update code:
class Solution {
public int fib(int N) {
int a = 0;
int b = 1;
if(N == 0) {
return a;
}
if(N == 1) {
return b;
}
for(int i = 2; i <= N; i++) {
int tmp = a + b;
a = b;
b = tmp;
}
return b;
}
}
Copy the codeSo we get the space complexity down to O(1), and the time complexity is O(n), just like with arrays.
This method is actually called Dynamic Programming, and the code written is very simple.
So let’s compare Recursion and DP:
Recursion is from large to small, layers of decomposition, until the base case decomposition can not be combined back up; DP is going from small to big, taking good notes and making progress.
Recursion + Cache = DP
How to take notes and how to take notes efficiently is the difficulty of DP.
Some people say that DP is trading space for time, but I don’t think so, and this problem is a good example.
When we solve the problem recursively, we can see that the space is O(n) on the stack, but with DP we can optimize the space to O(1), DP can do the double optimization of time and space.
In fact, the Fibonacci sequence has many applications in real life.
For example, in our company and many large companies, each task is given a score, with one score indicating that it will take about one day to complete, and then the score is divided into five types: 1, 2, 3, 5, 8. (If there is a task with more than 8 points, it needs to be broken down into less than 8 points, so that people can finish it within two weeks.) Since the tasks are endless and everyone’s time is limited, the team will have a meeting every time and pick up the most important tasks for everyone to do. Then everyone will pick up the corresponding tasks according to their available days.
A Wolf in sheep’s clothing
Then some students may think, this question is so easy, this is 2020, will the interview test?
A. It really does.
I just can’t give it to you in such a straightforward way.
Take the famous problem of climbing stairs:
How many ways can you take a staircase of N steps, one or two at a time?
The question thinks like this:
If you’re standing in the current position, you can only be standing in the previous layer, or two layers, so f of n is equal to f of n minus 1 plus f of n minus 2.
This question was actually asked in an interview when I was writing Python and used lambda Function to show off my skills:
f = lambda n: 1 if n in (1.2) else f(n- 1) + f(n2 -)
Copy the codeThe recursive method was too time intensive, so I wrote a version of for loop
def fib(n)
a.b = 1, 1
for i in range(n- 1):
a, b = b, a+b
return a
Copy the codeAnd then write a caching method:
def cache(f):
memo = {}
def helper(x):
if x not in memo:
memo[x] = f(x)
return memo[x]
return helper
@cache
def fibR(n):
if n==1 or n==2: return 1
return fibR(n- 1) + fibR(n2 -)
Copy the code(Tail recursion)
This is the tail recursion of the whole method.
So what’s so special about this one?
Tail-recursive is easily converted into the iterative version, which is automatically implemented by some intelligent compilers (not the explicit version, but the run-time version is run in iterative mode, using O(1) space).
So why is that?
Because you don’t have to backtrack when you come back, and this is the last step of the recursion, you don’t have to go up another level.
def fib(n, a=0, b=1):
if n==0: return a
if n==1: return b
return fib(n- 1, b, a+b)
Copy the codeFinally, I came up with my killer mace: Lambda and Reduce
fibRe = lambda n: reduce(lambda x, n: [x[1], x[0]+x[1]], range(n), [0.1])
Copy the codeAfter seeing the satisfaction of the interviewer’s face, I began to continue the in-depth conversation…
You can use seven or eight different methods to solve the same question. Analyze the advantages and disadvantages of each method and extend it to the areas where you can extend it to show off your solid basic skills. This interview is actually your chance to show off and fool the interviewer
This is all the content of this article, I do not know how you feel after reading? Let me know how you feel in the comments
Today this video has been done for half a day, if you like this form, please quality three lian:
Click to see, encourage me!
Writing comments makes me look very popular!
Forward forward forward forward, love her, give her!
Also want to see more data structures and algorithms with me, remember to pay attention to me, I am Tian Xiaoqi, algorithm is such a thing.
