preface

Recursion is a very important idea in the algorithm, the application is also very wide, small to factorial, and then used in the work, such as statistics folder size, as large as Google PageRank algorithm can be seen, is also a favorite test point of the interviewer

Recently I read a lot of recursion articles, harvest is not small, but I found that most of the online recursion articles are not comprehensive, the main problem is that most of the problem after solving did not give the corresponding time/space complexity, and time/space complexity is an important consideration of algorithm! The time complexity of recursive algorithms is generally difficult (induction is needed), in other words, if the algorithm complexity of recursion can be solved, the time complexity of other algorithms is basically no problem. In addition, the time complexity of recursive algorithm is not acceptable. If it is found that the time complexity is too large, we need to change our thinking to see if there is a better solution. This is the fundamental purpose, do not recurse for recursion!

This article tries to explain recursion from the following aspects

  1. What is recursion?
  2. Recursive algorithm general solution idea
  3. Actual practice (from beginner to advanced)

We strive to let the cognition of recursion on a new level, especially the essence of recursion: time complexity for a detailed analysis, will give you a very general solution to the recursive time complexity of the set, I believe you will have a harvest after reading

What is recursion

Simply put, if there is a situation in a function that calls the function itself, this phenomenon is called recursion.

Take the hierarchy function as follows: in factorial there is a call to factorial(n-1), so the function is recursive

public int factorial(int n) {
    if (n < =1) {
        return 1;
    }
    return n * factorial(n - 1)}Copy the code

Further analysis of “recursion”, there is “recursion” and “return”, “recursion” means that the problem is broken down into sub-problems to solve, sub-problems and then broken down into sub-problems,… , until the disassembled sub-problem does not need to be disassembled into finer sub-problems (that is, it can be solved), “return” means that the smallest sub-problem is solved, then its upper sub-problems are solved, the upper sub-problems are solved, and the upper sub-problems are naturally solved,…. Until the initial problem is solved, the text may be a little abstract, so let’s take stratum F (6) as an example to look at its “recursion” and “return”.

Same solution

Recursive algorithm general solution idea

In the last section we took a closer look at what recursion is, and we found that recursion has the following two characteristics, right

  1. A problem can be broken down into subproblems with the same solution, subproblems, in other words, they all call the same function
  2. A subproblem that has gone through layers of decomposition must eventually have a fixed value that can no longer be decomposed (i.e., the termination condition). If not, the subproblem will be decomposed indefinitely, and the problem is obviously unsolvable.

So the key to solving recursive problems is that we first need to judge whether the problem can be solved recursively according to the above two characteristics of recursion.

After judging that recursion can be used, let’s take a look at the basic routine of solving problems with recursion (four steps) :

  1. First define a function, clear the function of the function, because the characteristics of recursion is that the problem and the sub-problem will call the function itself, so once the function of this function is determined, then only to find the recursive relationship between the problem and the sub-problem
  2. Then, the relationship between the problem and the subproblem (namely, the recursive formula) is found. Since the problem and the subproblem have the same solution idea, the problem can be solved as long as the subproblem calls the function defined in Step 1. So-called relationship can best use a formula, such as f (n) = n * f (n -) so, if temporarily unable to draw a clear formula, also can be expressed in pseudo code, found after recurrence relation, again looking for an eventual solution of decomposition of subproblems, namely (critical conditions), to ensure that the problems won’t break down indefinitely. Since we have defined the function of this function in the first step, when the problem is divided into subproblems, the subproblems can call the function defined in step 1, which meets the recursive condition (calling itself in the function).
  3. Add the recursive formula of step 2 to the function defined in Step 1
  4. The last and crucial step is to deduce the time complexity according to the relationship between the problem and the sub-problem. If the recursive time complexity is found to be unacceptable, it is necessary to transform the idea to see if there is a more reliable solution

Doesn’t that sound simple, so let’s take a look at a few recursions, and see how we can use the steps above

Actual practice (from beginner to advanced)

A friendly

Input a positive integer n, output n! The value of the. Where n! = 123 *… Times n, that’s the factorial

So what do we do in the last video with four recursive steps

  1. We define this function, we know what this function does, and we know what this function does is we take n factorial, and then we take n minus 1, n minus 2 factorial and we call this function
/** ** find n factorial */
public int factorial(int n) {}Copy the code

The factorial relationship is relatively simple, we use F (n) to express n factorial, obviously F (n) = n * f(n-1), at the same time the critical condition is f(1) = 1, namely


3. Add the recursive formula of step 2 to the function defined in Step 1

/** ** find n factorial */
public int factorial(int n) {
    // The critical condition of the second step
    if (n < =1) {
        return 1;
    }

    // The recursive formula for the second step
    return n * factorial(n-1)}Copy the code

4. Calculate the time complexity because f(n) = n * f(n-1) = n * (n-1) *…. F of 1, n times, so n times.

Doesn’t it look like it’s going to make a little bit of sense, but of course it’s too easy, it’s easy to do, so let’s do a little bit more advanced

Introduction to the topic

A frog can jump one step at a time or two steps at a time, for example:Copy the code

There’s only one way to get to the first step: just jump the first step. There are two ways to jump up the second step: one step at a time; Or two steps at a time. How many ways can you jump to the NTH step?

Let’s go ahead and see how it works in four steps. Okay

1. Define a function that represents jumping up n steps

/** ** n pole step jump method */
public int f(int n) {}Copy the code

2. Look for the relationship between the question and the sub-question. At first glance, the relationship between the two things does not seem to have any clue. So the question becomes how to jump up n-1 and n-2 steps, and if f(n) is how to jump up n steps, So from the above analysis, it can be concluded that F (n) = F (n-1) + f(n-2), obviously this is the relationship between the problem we are looking for and the sub-problem, and obviously when n = 1, n = 2, namely jumping one or two steps is the final solution of the problem, so the recursive formula is


3. Add the recursive formula of the second step into the function defined in Step 1 with codes. The added function is as follows

/** ** n pole step jump method */
public int f(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return f(n-1) + f(n-2)}Copy the code

4. Calculation time complexity From the above analysis, it can be seen that F (n) meets the following formula


Fibonacci time complexity calculation involves the knowledge of advanced algebra, here we do not do detailed derivation, interested students can click here to view, we directly come to the conclusion

Given that time complexity is exponential, which is obviously unacceptable, let’s see why time complexity is so high. Suppose we want to calculate f(6), according to the recursive formula derived above, as shown below

You can see that there is a lot of double counting, f(3) is computed three times, and as n increases, the time of f(n) naturally increases exponentially

5. Optimization Since there are so many repeated calculations, we can think of saving the results of these intermediate calculations. If we encounter intermediate states that also need to be calculated in the subsequent calculation, we can directly query the saved results

public int f(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    // map is an intermediate key-value pair, key is n, value is f(n)
    if (map.get(n)) {
        return map.get(n)
    }
    return f(n-1) + f(n-2)}Copy the code

So what is the time complexity after the transformation? Because for every f(n) we have saved the intermediate state, there is no double calculation problem, so the time complexity is O(n), but because we use a key-value pair to save the intermediate calculation result, so the space complexity is O(n). The problem is solved at this point, but as ambitious programmers, we still have to ask, can space complexity continue to be optimized?

We use the top-down analysis method when analyzing the relationship between problem and sub-problem (F (n) = F (n-1) + f(n-2)), but in fact, we can use the bottom-up method when solving F (n). We can find the following rules through observation

f(1) = 1
f(2) = 2
f(3) = f(1) + f(2) = 3
f(4) = f(3) + f(2) = 5. f(n) = f(n- 1) + f(n2 -)
Copy the code

The lowest f(1), f(2) values are determined, and then f(3), F (4)… All the way up to f(n). So our code can be reconfigured as follows

public int f(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;

    int result = 0;
    int pre = 1;
    int next = 2;
    
    for (int i = 3; i < n + 1; i ++) {
        result = pre + next;
        pre = next;
        next = result;
    }
    return result;
}
Copy the code

The time complexity after transformation is O(n), and since we only defined two variables (pre, next) in the calculation process, the space complexity is O(1).

To sum up briefly: we need to use top-down thinking to analyze problems, and sometimes the bottom-up approach to solve problems can greatly improve the performance of the algorithm, thinking is more important than the conclusion

The primary problem

Let’s move on to the next classic problem: inverting a binary tree Inverts the left binary tree into the right binary tree

So let’s see how do we solve this problem using the recursive four steps that we summarized earlier

1. Define a function that represents flipping the binary tree with root as the root node

public static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(intx) { val = x; }}public TreeNode invertTree(TreeNode root) {}Copy the code

2. Find the relationship between the problem and the sub-problem and get the recursion formula. As we said before, the problem should be solved by top-down thinking, so let’s take the nodes 1, 2 and 3 in front and look at them

For nodes 2 and 3, flip the left and right nodes, and so on. For each root node, flip the left and right nodes, Invert (root) = invert(root->left) = invert(root->right); invert(root->left) = invert(root->right);

And of course the recursion terminates when the node is a leaf node (because leaves have no left and right nodes)

3. Add the recursive formula of step 2 to the function defined in Step 1

 public TreeNode invertTree(TreeNode root) {
    // Leaf results cannot be flipped
    if (root == null) {
        return null;
    }
    // Flip the left and right nodes under the left node
    TreeNode left = invertTree(root.left);
    // Flip the left and right nodes under the right node
    TreeNode right = invertTree(root.right);

    // After flipping the binary tree under the left and right nodes, flip the left and right nodes of the root node
    root.right = left;
    root.left = right;
    return root;
}
Copy the code

InvertTree = invertTree; invertTree = invertTree; invertTree = invertTree; invertTree = invertTree; invertTree = invertTree; invertTree = invertTree; invertTree = invertTree; Take a closer look at the next section of the above function

    TreeNode left = invertTree(root.left);
Copy the code

Starting from the root node, the flip function is continuously called to the left result until the leaf node, each call will be pushed, after the left node is called, out of the stack, and then the right node is pushed…. , the following figure shows that the stack size is 3, namely, the height of the tree. If it is a complete binary tree, the height of the tree is logn, namely, the space complexity is O(logn).

In the worst case, if the binary tree is as shown in the figure (only left nodes, no right nodes), then the height of the tree is the number of nodes n, and the space complexity is O(n). In general, the space complexity is O(n).

Intermediate title

As shown in the figure below, there are three pillars A, B and C from left to right. Among them, there are N disks stacked from small to large on pillar A. Now it is required that the disks on pillar A be moved to pillar C, during which there is only one principle: Only one plate can be moved at a time and the large plate cannot be on the small plate. Find the steps and the number of moves

So what do we do with this problem using our recursive four-step method

1. Define the recursive function of the problem and clarify its function. We define the function as: move n disks above A to C through B

// Move n disks from A to C via B
public void hanoid(int n, char a, char b, char c) {}Copy the code

First of all, if there are only two disks on pillar A, how can we move them

As we mentioned many times before, the relationship between a problem and its subproblems should be analyzed in a top-down manner, in which n disks are moved from B to pillar C, We can do this in three steps * think of the top n-1 disk as one disk, so we can do the same thing as we did with only two disks * Move the top n-1 disk through C to B * and then move the biggest disk under A to C * and then move the top N-1 disk over B The disks move from A to C

Someone asks how to move n-1 from C to B in the first step, repeat the above process, just move the top N-2 plates through A to B, then move the bottom plate of A to C, and finally move the top N-2 plates through A to B… In the process of finding a problem, do not expand the sub-problems layer by layer, do not analyze how to move N -3,n-4 to the hannotta problem, which will confuse you, as long as you find the relationship between a layer of problems and sub-problems can be expressed by recursion.

From the above analysis can be obtained

move(n from A to C) = move(n-1 from A to B) + move(A to C) + move(n-1 from B to C`)

Always get the recursion formula first, even if it’s pseudocode! That makes it A lot easier to write the third derivation, the termination condition and we can see that when the disk on A is gone it doesn’t move

3. Supplement functions of the function according to the above recursive pseudocode

// Move n disks from A to C via B
public void hanoid(int n, char a, char b, char c) {
    if (n <= 0) {
        return;
    }
    // Move the top n-1 disk through C to B
    hanoid(n-1, a, c, b);
    // Now move the largest disk under A to C
    move(a, c);
    // Move n-1 disks from B to C via A
    hanoid(n-1, b, a, c);
}

public void move(char a, char b) {
    printf("%c->%c\n", a, b);
}
Copy the code

It’s A little bit easier to understand in terms of what the function does, what the whole function is defined to do is to move n disks from A to C through B, and since I’ve defined what the function does, Then the n – 1 disc From C to B can naturally calls the function, function is very important, so certain functions according to their function to explain the function of recursive problem actually very good resolution, avoid by all means were unfolding on each child dead dig, so it’s into a trap of recursion, the computer will stack overflow, and the brain

4. Time complexity analysis It can be inferred from the function supplemented in the third step

f(n) = f(n-1) + 1 + f(n-1) = 2f(n-1) + 1 = 2(2f(n-2) + 1) + 1 = 2 * 2 * f(n-2) + 2 + 1 = 22 * f(n-3) + 2 + 1 = 22 * f(n-3) + 2 + 1 = 22 * (2f(n-4) + 1) = 23 * f(n-4) + 22 + 1 = …. // expand = 2n-1 + 2n-2 +…. + 1

Obviously the time complexity is O(2n), obviously the exponential level of time complexity is not acceptable, hannotta non-recursive solution is more complicated, you can go to the Internet to search

Advanced topic

In reality, many recursion problems in Dachang will not use the above relatively easy to understand the problem, more is the corresponding deformation of the recursion problem, look at the following problem

Cell division One cell divides every hour, one daughter at a time, and dies after the third hour. So how many cells are there in n hours?

So let’s use the recursive four steps

1. Define the recursive function of the problem and clarify the function We define the following function as the number of cells after n hours

public int allCells(int n) {}Copy the code

2. Next, we look for the relationship between the problem and its subproblems (i.e. the recursive formula). First, we look at all the cell division processes that a cell undergoes from birth to death

A represents the initial state of the cell, B represents the juvenile state (the cell divides once), and C represents the mature state (the cell divides twice). F (n) represents the number of cells decomposed at the NTH hour. Fa (n) represents the number of cells in the initial state at the NTH hour. Fb (n) is the number of cells in the juvenile state at hour NTH and FC (n) is the number of cells in the mature state at hour NTH so f(n) = FA (n) + Fb (n) + FC (n) so what is FA (n) equal to, Take n = 4 (that is, a cell goes through its entire life cycle)

Look at the picture above carefully

It can be seen that FA (n) = FA (n-1) + Fb (n-1) + FC (n-1), when n = 1, obviously FA (1) = 1

So fb(n) is equal to fa(n-1). When n = 1, fb(n) = 0

And fc(n), if you look at the figure below, fc(n) is fb(n-1). Fc (n) = 0 when n = 1,2

To sum up, the recursion formula is as follows

f(n) = fa(n) + fb(n) + fc(n)




3. According to the above recursive formula, we supplement the function of the function

public int allCells(int n) {
    return aCell(n) + bCell(n) + cCell(n);
}

/** * Number of cells in state A at hour NTH */
public int aCell(int n) {
    if(n==1) {return 1;
    }else{
        return aCell(n-1)+bCell(n-1)+cCell(n-1); }}/** * Number of cells in state B at hour NTH */
public int bCell(int n) {
    if(n==1) {return 0;
    }else{
        return aCell(n-1); }}/** * The number of cells in state C at the NTH hour */
public int cCell(int n) {
    if(n==1 || n==2) {return 0;
    }else{
        return bCell(n-1); }}Copy the code

If you have the right idea, it’s a lot easier to translate the recursion into code, but it also tells us that maybe we can’t see the recursion at the moment, so we can draw a picture to see the pattern

According to the recursive formula of the second step, we know that F (n) = 2aCell(n-1) + 2aCell(n-2) + aCell(n-3)

The time complexity of frog jumping steps is exponential before, and this equation is obviously more complex than the previous recursive formula (F (n) = F (n-1) + f(n-2)), so it is also exponential

conclusion

Most of recursive problem actually still have can track, according to the summary before the four steps of the recursive solution can be more smoothly to solve the recursive problem, some more complex recursive problems often begin, we need to draw diagrams, observe the law, it can help us quickly find order, draw a recursive formula, once you know the recursive formula, It is much easier to turn it into recursive code, many large factory recursion examination questions and can not simply see the law of recursion, often on the basis of recursion more deformation, but ten thousand times does not leave its ancestor, we use top-down analytical thinking, more practice, believe that recursion is not what difficult

Welcome to the public account “code sea”!