A necessary skill (algorithm) for contemporary programmers: recursive explanation

preface

Recursion is a very important algorithm idea. You need to master it whether you are front-end development or back-end development. In daily work, recursive algorithms are needed to count the size of folders, parse xml files and so on. It's too basic and important, which is why interviewers often ask us to write recursive algorithms. In this article, I will learn recursive algorithm with you~

  • What is recursion?
  • Characteristics of recursion
  • Relationship between recursion and stack
  • Recursive application scenario
  • Recursive problem solving ideas
  • leetcode case study
  • Possible problems and solutions of recursion

What is recursion?

Recursion, in computer science, refers to a method of solving a problem by repeatedly decomposing the problem into similar subproblems. In short, recursion is expressed as a function calling the function itself. In Zhihu, I saw an example of metaphor recursion, which I think is very vivid. Let's have a look:

The most appropriate metaphor for recursion is to look it up in a dictionary. The dictionary we use is recursive in itself. In order to explain a word, we need to use more words. When you look up a word and find that a word in the explanation of the word still doesn't understand, you start to look up the second word. Unfortunately, there are still words you don't understand in the second word, so look up the third word and keep looking up until you can fully understand the explanation of a word. Then the recursion comes to an end, and then you start to step back and understand each word you checked one by one. Finally, you understand the meaning of the first word.

Let's try the water. Let's take a recursive code example, as follows:

public int sum(int n) {
    if (n <= 1) {
        return 1;
    } 
    return sum(n - 1) + n; 
} 

Characteristics of recursion

In fact, recursion has two remarkable characteristics, termination condition and self call:

  • Self call: the original problem can be decomposed into subproblems. The solution methods of subproblems and the original problem are the same, that is, they all call their own same function.
  • Termination condition: recursion must have a termination condition, that is, it cannot call itself in an infinite loop.

Combined with the above demo code examples, let's see the characteristics of recursion:

Relationship between recursion and stack

In fact, the process of recursion can be understood as the process of entering and leaving the stack. This metaphor is just for the convenience of readers to better understand recursion. The stack entry and exit diagram of sum (n=3) calculated by the above code example is as follows:

To make it easier to understand, let's take a look at the recursive execution process of function sum (n=5), as follows:

  • When calculating sum (5), put sum (5) on the stack first, then split the original problem sum (5) into sub problem sum (4), and then put it on the stack until the termination condition sum (n=1) = 1.
  • After sum (1) is out of the stack, sum (2) starts out of the stack, and then sum (3).
  • Finally, sum (1) is LIFO, and sum (5) is FIFO, so the recursive process can be understood as the stack in and out process~

Classic application scenario of recursion

What problems can we consider using recursion to solve? That is, what are the general application scenarios of recursion?

  • Factorial problem
  • Binary tree depth
  • Hanoi Tower problem
  • Fibonacci sequence
  • Quick sort, merge sort (divide and conquer algorithm also uses recursion)
  • Traverse the file and parse the xml file

Recursive problem solving ideas

There are generally three steps to solve the recursion problem, which are:

  • The first step is to define the function
  • The second step is to find the recursive termination condition
  • The second step is the equivalence relation of recursive function

This three board axe for recursive problem solving is a little abstract. Let's take factorial recursion as an example~

1. Define function

To define the function of a function, that is to say, what does your function do? In other words, you need to know what the original problem of recursion is? For example, you need to solve the factorial problem. The function defined is the factorial of n, as follows:

//Factorial of n (n is a natural number greater than 0)
int factorial (int n){

} 

2. Find recursive termination conditions

A typical feature of recursion is that there must be a termination condition, that is, it cannot call itself indefinitely. Therefore, when you need to find the condition of recursion, you need to use recursion to solve the problem. For example, for factorial problems, when n=1, there is no need to recurse down. You can jump out of the loop. n=1 can be used as the termination condition of recursion, as follows:

//Factorial of n (n is a natural number greater than 0)
int factorial (int n){
    if(n==1){
      return 1;
    }
} 

3. Equivalent relation of recursive function

The "original meaning" of recursion is that the original problem can be divided into sub problems of the same kind and easier to solve, that is, "the original problem and sub problems can be expressed by the same functional relationship. This step is equivalent to finding the relationship between the original problem and sub problems. How to express this function clearly with a formula". The formula of factorial can be expressed as f(n) = n * f(n-1). Therefore, the recursive program code of factorial can be written as follows:

int factorial (int n){
    if(n==1){
      return 1;
    }
    return n * factorial(n-1);
} 

Note that not all the equivalence relations of recursive functions are as simple as factorial, which can be deduced at once. We need more contact, more accumulation, more thinking and more practice~

leetcode case study

Let's analyze a classic topic of leetcode recursion~

The original title is linked here, ha: https://leetcode-cn.com/probl...

"Title:" flip a binary tree.

Input:

 4
   /   
  2     7
 /    / 
1   3 6   9 

Output:

 4
   /   
  7     2
 /    / 
9   6 3   1 

Let's follow the three board axe of recursive problem solving above:

"1. Define function"

The function function (that is, the original problem of recursion) gives a tree and then flips it. Therefore, the function can be defined as:

//Flip a binary tree
public TreeNode invertTree(TreeNode root) {
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ 

"2. Find recursive termination conditions"

When won't the tree turn over? Of course, when the current node is null or the current node is a leaf node. Therefore, adding the termination condition is:

//Flip a binary tree
public TreeNode invertTree(TreeNode root) {
    if(root==null || (root.left ==null && root.right ==null)){
       return root;
    }
} 

"3. Equivalent relation of recursive function"

In the original question, if you want to flip a tree, can you split it into sub problems and flip its left sub tree and right sub tree respectively? The sub problem of flipping its left subtree can be divided into flipping its left subtree and flipping its right subtree? Then flip all the way to the leaf node. Well, look at the picture and understand it~

First, if you want to flip the tree with root node 4, you need to "flip its left subtree (root node 2) and right subtree (root node 7)". This is the recursive "delivery" process

Then, the tree with root node 2 is not a leaf node. You need to continue to "flip its left subtree (root node 1) and right subtree (root node 3)". Because nodes 1 and 3 are "leaf nodes", they return. This is also a recursive "recursive" process~

Similarly, a tree with a root node of 7 is not a leaf node. You need to flip its left subtree (root node of 6) and right subtree (root node of 9). Because nodes 6 and 9 are leaf nodes, they also return.

After the left subtree (root node 2) and the right subtree (root node 7) are flipped, these steps will "return", that is, the recursive return process, and the task of flipping the tree is completed~

Obviously, "recurrence relation" is:

invertTree(root)= invertTree(root.left) + invertTree(root.right); 

Therefore, it is easy to get the following code:

//Flip a binary tree
public TreeNode invertTree(TreeNode root) {
    if(root==null || (root.left ==null && root.right ==null){
       return root;
    }
    //Flip left subtree
    TreeNode left = invertTree(root.left);
    //Flip right subtree
    TreeNode right= invertTree(root.right);
} 

There is a place to note in the code here. After flipping the left and right subtrees of a tree, you have to exchange the reference positions of its left and right subtrees.

 root.left = right;
 root.right = left; 

Therefore, the "ultimate solution code" of leetcode, a classic recursive problem, is as follows:

class Solution {
    public TreeNode invertTree(TreeNode root) {
         if(root==null || (root.left ==null && root.right ==null)){
           return root;
         }
         //Flip left subtree
         TreeNode left = invertTree(root.left);
         //Flip right subtree
         TreeNode right= invertTree(root.right);
         //Exchange position of left and right subtrees~
         root.left = right;
         root.right = left;
         return root;
    }
} 

Take the ultimate solution code to leetcode and submit it. It's passed~

Problems with recursion

  • Too many levels of recursive calls lead to stack overflow
  • Recursive repeated calculation leads to low efficiency

Stack overflow problem

  • Each function call allocates space in the memory stack, and the stack capacity of each process is limited.
  • When there are too many levels of recursive calls, the capacity of the stack will be exceeded, resulting in overflow of the call stack.
  • In fact, we also discussed in the previous section that the recursive process is similar to that of out of the stack into the stack. If the number of recursions is too many, the deeper the stack needs to be. Finally, the stack capacity is really not enough

"Code examples are as follows:"

/**
 * Recursive stack overflow test
 */
public class RecursionTest {

    public static void main(String[] args) {
        sum(50000);
    }
    private static int sum(int n) {
        if (n <= 1) {
            return 1;
        }
        return sum(n - 1) + n;
    }
} 

"Operation result:"

Exception in thread "main" java.lang.StackOverflowError
 at recursion.RecursionTest.sum(RecursionTest.java:13) 

How to solve this stack overflow problem? First, you need to "optimize your recursion". Do you really need to call recursion so many times? If you really need it, first "increase the stack space memory of the JVM". If it still doesn't work, you need to abandon recursion and "optimize it for other solutions"~

Repeated calculation leads to low program efficiency

Let's take another look at the classic frog step jumping problem: a frog can jump up one step or two steps at a time. Find out the total number of jumping methods for the frog to jump up an n-step step.

Most readers can easily think of the following recursive code to solve it:

class Solution {
    public int numWays(int n) {
    if (n == 0){
       return 1;
     }
    if(n <= 2){
        return n;
    }
    return numWays(n-1) + numWays(n-2);
    }
} 

However, if you go to leetcode to submit it, there will be a problem. It is beyond the time limit

Why did you time out? Where does recursion take? First draw the "recursive tree" to see:

  • To calculate the original problem f(10), we need to calculate the subproblems f(9) and f(8)
  • Then, to calculate f(9), we must first calculate the subproblems f(8) and f(7), and so on.
  • The recursive tree does not terminate until f(2) and f(1).

Let's take a look at the recursive time complexity first, "recursive time complexity = time to solve a sub problem * number of sub problems"

  • A subproblem time = f (n-1) + F (n-2), which is an addition operation, so the complexity is "O(1)";
  • The number of problems = the total number of recursive tree nodes, and the summary point of recursive tree = 2^n-1, so it is the complexity "O(2^n)".

Therefore, the time complexity of frog jumping order and recursive solution = O(1) * O(2^n) = O(2^n), which is exponential and explosive. "If n is large, timeout is normal.".

Looking back, if you look closely at this recursive tree, you will find that there are "a lot of repeated calculations". For example, f (8) is calculated twice and f (7) is calculated three times So the reason why this recursive algorithm is inefficient is that there are a lot of repeated calculations!

"So, how to solve this problem?"

Since there are a lot of double counting, we can save the calculated answers first, that is, make a memo. If necessary next time, check the memo first. If there is any, just take it directly. If there is no memo, we can calculate again, which can save the time of double counting! This is the "solution with memo"

Let's take a look at "recursive solution with memo"~

Generally, an array or a hash map is used as the memo.

Suppose f(10) is solved with "Memo", let's draw a recursive tree again:

"Step 1", f (10) = f(9) + f(8), f(9) and f (8) need to be calculated and then added to the memo, as follows:

"Step 2," f(9) = f(8) + f(7),f(8) = f (7) + f(6). Since f(8) is already in the memo, it can be omitted. Both f (7) and f(6) need to be calculated and added to the memo~

"Step 3," f(8) = f (7) + f(6), it is found that f(8), f (7) and f(6) are all on the memo, so they can be cut off.

So, using the memo recursive algorithm, the recursive tree becomes a bare trunk, as follows:

For the recursive algorithm with memo, the number of subproblems = the number of tree nodes = n, and it is O(1) to solve a subproblem, so the time complexity of the recursive algorithm with memo is O(n). Next, we use the recursive algorithm with "Memo" to solve the timeout problem of the frog jumping problem ~, and the code is as follows:

public class Solution {
    //Use a hash map to act as a memo
    Map<Integer, Integer> tempMap = new HashMap();
    public int numWays(int n) {
        //n = 0 ; is also considered as one kind
        if (n == 0) {
            return 1;
        }
        if (n <= 2) {
            return n;
        }
        //First judge whether it has been calculated, that is, check whether there is a memo
        if (tempMap.containsKey(n)) {
            //If the memo has been calculated, it will be returned directly
            return tempMap.get(n);
        } else {
            //If the memo is not, that is, it has not been calculated, perform recursive calculation, save the results in the memo map, and get the remainder of 1000000007 (this is specified in the leetcode title)
            tempMap.put(n, (numWays(n - 1) + numWays(n - 2)) % 1000000007);
            return tempMap.get(n);
        }
    }
} 

Go to leetcode and submit it, as shown in the figure. It's stable:

Write at the end

Since you can see here that this article is still helpful to you, can Xiaobian ask for a little praise for you.

Extended learning reading

Still worried about the algorithm? Then you shouldn't have seen this 70k Star Note on Github
Video: Violent recursive algorithm

After reading three things ❤️

========

If you think this article is very helpful to you, I'd like to invite you to help me with three small things:

Like, forward, and have your "praise and comments" is the driving force of my creation.

Pay attention to the official account "Java Doudi" and share original knowledge from time to time.

At the same time, we can look forward to the follow-up articles 🚀

Tags: Java Spring Algorithm Back-end

Posted by NoMansLand on Sun, 08 May 2022 06:34:17 +0300