Recursion is done in one article! Super detailed diagram, read no longer afraid of the interviewer!

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

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

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

2. Finding the relationship between problems and subproblems The factorial relationship is relatively simple, we express n factorial by f(n), It is obvious that F (n)= n * f(n-1), and the critical condition is f(1) = 1, i.e. F (n)= {1, n = 1 ∗ f(n − 1) f(n)= \begin{cases} 1, N = 1 \ \ n * f (n – 1) \ end {cases} f (n) = {1, n = 1 n ∗ f (n – 1)

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. Find 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

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

/** ** 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

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

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(n-2)
Copy the code

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 primary problem

Let’s move on to the classic problem of reversing binomial trees

Invert the left binary tree to 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

Start from the root node and continue to call the flip function on 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).



As an aside, this problem caused a stir when Max Howell, the creator of Homebrew, couldn’t solve it and was rejected by Google, which means that if you solve it, you’ll be ahead of the world’s most powerful person

Intermediate title

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

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

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, find the relationship between the problem and its subproblems (i.eThe recursive formula)

Let’s start by looking at all the cell division that a cell goes through 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)

F a (n) = {f a (n − 1) + f b (n − 1) + f c (n − 1) 1, N = 1, f (n – 1) + f (n – 2) f_a (n) = \ begin {cases} f_a (n – 1) + f_b f_c (n – 1) + (n – 1) \ \ 1. N = 1 \ \ f (n – 1) + f (n – 2) \ end fa (n) = {cases} ⎩ ⎪ ⎨ ⎪ ⎧ fa (n – 1) + fb (n – 1) + fc (n – 1) 1, n = 1, f (n – 1) + f (n – 2)

F (n) b = {(n – 1) 0 f a, n = 1 f_b (n) = \ begin {cases} f_a \ \ 0 (n – 1), n = 1 \ \ \ end fb (n) = {cases} {fa (n – 1) 0, n = 1

F (n) c = {(n – 1) 0 f b, n = 1 0, n = 2 f_c (n) = \ begin {cases} f_b (n – 1) \ \ 0, \ \ 0 n = 1. N =2 \\ \end{cases} fc(n)= op ⎪⎨⎪⎧fb(n−1)0,n=10,n=2

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