编程知识 cdmana.com

Recursive explanation: the essential skills (algorithms) of contemporary programmers

Preface

Recursion is a very important algorithm , Whether you're a front-end Developer , Or back-end development , You need to master it . In daily work , Count the size of the folder , analysis xml Documents, etc. , We need to use recursive algorithms . It's so basic, so important , That's why in an interview , Interviewers often ask us to handwrite recursive algorithms . This article , I will learn recursive algorithm with you ~

  • What is recursion ?
  • The characteristics of recursion
  • The relationship between recursion and stack
  • Recursive application scenarios
  • How to solve problems recursively
  • leetcode case analysis
  • Possible problems and solutions of recursion

What is recursion ?

recursive , In computer science, it refers to a method to solve a problem by repeatedly decomposing a problem into a similar subproblem . Simply speaking , Recursion is represented by the function calling the function itself . In Zhihu, I see an example of metaphor recursion , I think it's very figurative , Let's have a look :

*

The most appropriate metaphor for recursion , Look it up in a dictionary . The dictionary we use , It's recursive in itself , To explain a word , More words need to be used . When you look up a word , I found that a word in the explanation of this word still doesn't understand , So you start looking up the second word , unfortunately , There are still words in the second word that I don't understand , So look up the third word , Go on like this , Until there's a word that you can fully understand , So recursion comes to an end , And then you start to step back , Understand each word one by one , Final , You get the meaning of the first word .

*

Come and try the water , Take a look at a recursive code example , as follows :

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

The characteristics of recursion

actually , Recursion has two distinct features , Termination conditions and self calls :

  • Call yourself : The original problem can be decomposed into subproblems , The solution of subproblem and original problem is the same , That is, they all call the same function of their own .
  • Termination conditions : Recursion must have a termination condition , That is, you can't call itself in an infinite loop .

Combined with the above demo Code example , Look at the features of recursion :

 The basic algorithm necessary for programmers : Recursion details

The relationship between recursion and stack

Actually , The process of recursion , It can be understood as the process of entering and leaving the stack , The metaphor is , It's just for the convenience of readers and friends to understand recursion better . The above code example calculates sum(n=3) The picture of the entrance and exit of the stack is as follows :

 The basic algorithm necessary for programmers : Recursion details

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

 The basic algorithm necessary for programmers : Recursion details

  • Calculation sum(5) when , First sum(5) Push , And then the original question sum(5) Split into subproblems sum(4), Go back to the stack , Until the termination condition sum(n=1)=1, And it started to come out of the stack .
  • sum(1) After leaving the stack ,sum(2) Start out stack , next sum(3).
  • Finally ,sum(1) It's last in, first out ,sum(5) First in, then out , So recursive process can be understood as stack in and out process ~

The classic application scenario of recursion

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

  • Factorial problem
  • The depth of the binary tree
  • The hanotta problem
  • Fibonacci sequence
  • Quick sort 、 Merge sort ( Divide and conquer algorithm also uses recursion )
  • Traversal file , analysis xml file

How to solve problems recursively

To solve the problem of recursion is usually a three-step process , Namely :

  • First step , Define function function
  • The second step , Looking for recursive termination conditions
  • The second step , The equivalent relation of recursive function

This recursive three board axe to understand a little abstract , Let's take factorial recursion as an example ~

1. Define function function

Define function function , That is to say , What's your function for , What to do , let me put it another way , You need to know what the original recursion problem is ? For example, you need to solve factorial problems , The function defined is n The factorial , as follows :

//n The factorial (n For more than 0 The natural number of )
int factorial (int n){

} 

2. Looking for recursive termination conditions

A typical feature of recursion is that there must be a termination condition , That is, you can't call itself in an infinite loop . therefore , When using recursive thinking to solve problems , You need to find out what the recursive termination condition is . For example, factorial problems , When n=1 When , No more recursion , You can jump out of the loop ,n=1 It can be used as the termination condition of recursion , as follows :

//n The factorial (n For more than 0 The natural number of )
int factorial (int n){
    if(n==1){
      return 1;
    }
} 

3. The equivalent relation of recursive function

Recursive 「 Original meaning 」, That is, the original problem can be split into sub problems of the same kind and easier to solve , namely 「 Both the original problem and the subproblem can be expressed by the same function relation . The equivalent relation of recursive function , This step is equivalent to finding the relationship between the original problem and the subproblem , How to express this function clearly with a formula 」. The formula of factorial can be expressed as f(n) = n * f(n-1), therefore , Factorial recursive program code can be written like this , as follows :

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

「 Attention! 」, Not all the equivalent relations of recursive functions are as simple as factorials , You can deduce it all at once . We need more contact with , More than accumulation , Think more , Practice recursion more ~

leetcode case analysis

To analyze a piece of leetcode The classic topic of recursion ~

*

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

*

「 subject :」  Turn over a binary tree .

Input :

 4
   /   
  2     7
 /    / 
1   3 6   9 

Output :

 4
   /   
  7     2
 /    / 
9   6 3   1 

Let's follow the three axes of recursion :

「1. Define function function 」

The functionality ( The original problem of recursion is ), Give a tree , And then flip it over , 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. Looking for recursive termination conditions 」

When does this tree not have to turn over ? Of course, the current node is null Or when the current node is a leaf node . therefore , Plus 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. The equivalent relation of recursive function 」

The original problem is you want to flip a tree , Can it be broken down into subproblems , Flip its left and right subtrees separately ? Flip the left subtree of subproblem , Can it be divided into , Flip the left subtree of its left subtree and the right subtree of its left subtree ? And then flip it all the way to the leaf node . Um. , Look at the picture to understand ~

 The basic algorithm necessary for programmers : Recursion details

First , You want to flip the root node to 4 The tree of , Need 「 Flip its left subtree ( The root node is 2) And right subtree ( The root node is 7)」. This is recursive 「 Deliver 」 The process of

 The basic algorithm necessary for programmers : Recursion details

so what , The root node is 2 The tree of , It's not a leaf node , You need to continue 「 Flip its left subtree ( The root node is 1) And right subtree ( The root node is 3)」. Because of the node 1 and 3 All are 「 Leaf node 」 了 , So I went back . This is also recursive 「 Deliver 」 The process of ~

 The basic algorithm necessary for programmers : Recursion details

Empathy , The root node is 7 The tree of , It's not a leaf node , You need to flip 「 Its left subtree ( The root node is 6) And right subtree ( The root node is 9)」. Because of the node 6 and 9 It's all leaf nodes , So it's back .

 The basic algorithm necessary for programmers : Recursion details

The left subtree ( The root node is 2) And right subtree ( The root node is 7) It's all flipped over , These steps are 「 Return 」, That is, the regression process of recursion , The task of flipping the tree is completed ~

 The basic algorithm necessary for programmers : Recursion details

obviously ,「 Recurrence relation 」 Namely :

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

therefore , It's 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 the left subtree 
    TreeNode left = invertTree(root.left);
    // Flip the right subtree 
    TreeNode right= invertTree(root.right);
} 

There's a point in the code that needs attention , Turn over the left and right subtrees of a tree , We also exchange the reference positions of its left and right subtrees .

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

therefore ,leetcode This recursive classic topic 「 The ultimate solution code 」 as follows :

class Solution {
    public TreeNode invertTree(TreeNode root) {
         if(root==null || (root.left ==null && root.right ==null)){
           return root;
         }
         // Flip the left subtree 
         TreeNode left = invertTree(root.left);
         // Flip the right subtree 
         TreeNode right= invertTree(root.right);
         // Left and right subtrees switch positions ~
         root.left = right;
         root.right = left;
         return root;
    }
} 

Take the ultimate solution code leetcode Submit a , Pass through ~

 The basic algorithm necessary for programmers : Recursion details

The problem with recursion

  • Too many levels of recursive calls , This leads to a stack overflow problem
  • Recursive repeated calculation , It leads to inefficiency

Stack overflow problem

  • Each function call allocates space in the memory stack , The stack capacity of each process is limited .
  • When there are too many levels of recursive calls , It will exceed the capacity of the stack , This causes the call stack to overflow .
  • Actually , We also discussed in the previous section , The recursive process is similar to putting out of the stack , If you recurs too many times , The deeper the stack needs to be , Finally, the stack capacity is really not enough

「 The code example is 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;
    }
} 

「 Running results :」

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

How to solve this stack overflow problem ? The first thing you need to 「 Optimize your recursion 」, You really need to call recursively so many times ? If you really need it , Just a little bit 「 turn up JVM Stack space memory 」, If it still doesn't work , You need to get rid of recursion ,「 Optimize for other solutions 」 Slightly ~

Repeat the calculation , It leads to inefficiency of the program

Let's look at a classic frog step jumping problem : A frog can jump up at a time 1 Stepped steps , You can jump on it 2 Stepped steps . Ask the frog to jump on one n How many jumps are there in the steps .

The vast majority of reader friends , It's easy to think of the following recursive code to solve :

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

But what? , Go to leetcode Submit a , There's a problem , It's beyond the time limit

 The basic algorithm necessary for programmers : Recursion details

Why is it overtime ? Where does recursion take ? Draw... First 「 Recursive tree 」 have a look :

 The basic algorithm necessary for programmers : Recursion details

  • To calculate the original problem f(10), We need to calculate the subproblem first f(9) and f(8)
  • And then calculate f(9), We have to work out the subproblem first f(8) and f(7), And so on .
  • Until f(2) and f(1), The recursive tree ends .

Let's take a look at the time complexity of recursion ,「 Recursive time complexity = Time to solve a sub problem * Number of sub questions 」

  • A sub question time = f(n-1)+f(n-2), It's an addition operation , So the complexity is  「O(1)」;
  • Number of questions = The total number of recursive tree nodes , The summary of recursive trees = 2^n-1, So it's complexity 「O(2^n)」.

therefore , The frog jumps the steps , The time complexity of recursive solution = O(1) * O(2^n) = O(2^n), It's exponential , Explosive growth of ,「 If n If it's bigger , Overtime is normal 」.

Come back to , You look at this recursive tree , You will find that there is 「 A lot of double counting 」, such as f(8) Was counted twice ,f(7) It's been recalculated 3 Time ... So the reason why this recursive algorithm is inefficient , There's a lot of double counting !

「 that , How to solve this problem ?」

Since there is a lot of double counting , Then we can save the calculated answers first , Make a memo , When you need it next time , Go first 「 Memorandum 」 Check it out , If there is , Just take it directly , The memo doesn't count , So you can save the time of recalculation ! This is it. 「 Solution with memo 」

Let's take a look 「 Recursive solution with memo 」 Well ~

Usually use an array or a hash map Act as this 「 Memorandum 」.

hypothesis f(10) Solution plus 「 Memorandum 」, Let's draw a recursive tree again :

「 First step 」,f(10)= f(9) + f(8),f(9) and f(8) All need to be calculated , And then add it to the memo , as follows :

 The basic algorithm necessary for programmers : Recursion details

「 The second step ,」 f(9) = f(8)+ f(7),f(8)= f(7)+ f(6), because f(8) It's in the memo , So you can save ,f(7),f(6) All need to be calculated , Add it to the memo ~

 The basic algorithm necessary for programmers : Recursion details

「 The third step ,」 f(8) = f(7)+ f(6), Find out f(8),f(7),f(6) It's all on the memo , So you can cut it off .

 The basic algorithm necessary for programmers : Recursion details

So , Using the memo recursion algorithm , Recursive trees become bare trunks , as follows :

 The basic algorithm necessary for programmers : Recursion details

belt 「 Memorandum 」 The recursive algorithm of , Number of sub questions = Node number =n, Solving a sub problem is still O(1), therefore 「 belt 「 Memorandum 」 The time complexity of recursive algorithm is O(n)」. The next? , We use belts 「 Memorandum 」 The recursive algorithm of the code , To solve the problem of time-out for the frog step jumping problem ~, The code is as follows :

public class Solution {
    // Use hash map, Act as a memorandum 
    Map<Integer, Integer> tempMap = new HashMap();
    public int numWays(int n) {
        // n = 0  Also calculate 1 Kind of 
        if (n == 0) {
            return 1;
        }
        if (n <= 2) {
            return n;
        }
        // First, judge whether it has been calculated , Let's see if the memo has 
        if (tempMap.containsKey(n)) {
            // The memo has , That is to say , Go straight back to 
            return tempMap.get(n);
        } else {
            //  The memo didn't , That is, it has not been calculated , Perform recursive computation , And save the results in a memo map in , Yes 1000000007 Remainder ( This is leetcode The title is specified )
            tempMap.put(n, (numWays(n - 1) + numWays(n - 2)) % 1000000007);
            return tempMap.get(n);
        }
    }
} 

Go to leetcode Submit a , Pictured , The steady :

 The basic algorithm necessary for programmers : Recursion details  The basic algorithm necessary for programmers : Recursion details

At the end

Now that you can see it, this article is helpful to you , Can Xiaobian ask for a little praise for you .

Extended learning reading

Still worrying about algorithms ? So you haven't seen this one yet Github On 70k Star Notes
video : Brute force recursive algorithm

After reading three things ️

========

If you think this is helpful for you , I'd like to invite you to do me three little favors :

give the thumbs-up , forward , There's your 『 Praise and comment 』, That's what motivates me to create .

Official account 『 Java Doudi 』, Share original knowledge from time to time .

At the same time, we can look forward to the following articles ing

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

Scroll to Top