编程知识 cdmana.com

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

{"type":"doc","content":[{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":" Preface "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" 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 ~"}]},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" What is recursion ?"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The characteristics of recursion "}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The relationship between recursion and stack "}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Recursive application scenarios "}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" How to solve problems recursively "}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"leetcode case analysis "}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Possible problems and solutions of recursion "}]}]}]},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":" What is recursion ?"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" 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 :"}]},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"*"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" 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 ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"*"}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Come and try the water , Take a look at a recursive code example , as follows :"}]},{"type":"codeblock","attrs":{"lang":null},"content":[{"type":"text","text":"public int sum(int n) {\n    if (n <= 1) {\n        return 1;\n    } \n    return sum(n - 1) + n; \n}\n"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":" The characteristics of recursion "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" actually , Recursion has two distinct features , Termination conditions and self calls :"}]},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" 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 ."}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Termination conditions : Recursion must have a termination condition , That is, you can't call itself in an infinite loop ."}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Combined with the above demo Code example , Look at the features of recursion :"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/ed/ed0df7a912bda93939cec59b575875d4.png","alt":" The basic algorithm necessary for programmers : Recursion details ","title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":" The relationship between recursion and stack "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" 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 :"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/6e/6e9d053109ebbf4157ec21cdab40293d.jpeg","alt":" The basic algorithm necessary for programmers : Recursion details ","title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" To make it easier to understand , Let's take a look function sum(n=5) The recursive execution of , as follows :"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/ba/ba956794dbb7669b03947a5531895a39.jpeg","alt":" The basic algorithm necessary for programmers : Recursion details ","title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" 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 ."}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"sum(1) After leaving the stack ,sum(2) Start out stack , next sum(3)."}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" 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 ~"}]}]}]},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":" The classic application scenario of recursion "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" What problems can we consider using recursion to solve ? That is, what are the application scenarios of recursion ?"}]},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Factorial problem "}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The depth of the binary tree "}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The hanotta problem "}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Fibonacci sequence "}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Quick sort 、 Merge sort ( Divide and conquer algorithm also uses recursion )"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Traversal file , analysis xml file "}]}]}]},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":" How to solve problems recursively "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" To solve the problem of recursion is usually a three-step process , Namely :"}]},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" First step , Define function function "}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The second step , Looking for recursive termination conditions "}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The second step , The equivalent relation of recursive function "}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" This recursive three board axe to understand a little abstract , Let's take factorial recursion as an example ~"}]},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":"1. Define function function "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" 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 :"}]},{"type":"codeblock","attrs":{"lang":null},"content":[{"type":"text","text":"//n The factorial (n For more than 0 The natural number of )\nint factorial (int n){\n\n}\n"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":"2. Looking for recursive termination conditions "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" 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 :"}]},{"type":"codeblock","attrs":{"lang":null},"content":[{"type":"text","text":"//n The factorial (n For more than 0 The natural number of )\nint factorial (int n){\n    if(n==1){\n      return 1;\n    }\n}\n"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":"3. The equivalent relation of recursive function "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Recursive "},{"type":"text","marks":[{"type":"strong"}],"text":"「 Original meaning 」"},{"type":"text","text":", That is, the original problem can be split into sub problems of the same kind and easier to solve , namely "},{"type":"text","marks":[{"type":"strong"}],"text":"「 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 」"},{"type":"text","text":". 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 :"}]},{"type":"codeblock","attrs":{"lang":null},"content":[{"type":"text","text":"int factorial (int n){\n    if(n==1){\n      return 1;\n    }\n    return n * factorial(n-1);\n}\n"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"「 Attention! 」"},{"type":"text","text":", 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 ~"}]},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":"leetcode case analysis "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" To analyze a piece of leetcode The classic topic of recursion ~"}]},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"*"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The original title is linked here :https://leetcode-cn.com/problems/invert-binary-tree/"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"*"}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"「 subject :」"},{"type":"text","text":"  Turn over a binary tree ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Input :"}]},{"type":"codeblock","attrs":{"lang":null},"content":[{"type":"text","text":"     4\n   /   \\\n  2     7\n / \\   / \\\n1   3 6   9\n"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Output :"}]},{"type":"codeblock","attrs":{"lang":null},"content":[{"type":"text","text":"     4\n   /   \\\n  7     2\n / \\   / \\\n9   6 3   1\n"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Let's follow the three axes of recursion :"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"「1. Define function function 」"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The functionality ( The original problem of recursion is ), Give a tree , And then flip it over , therefore , The function can be defined as :"}]},{"type":"codeblock","attrs":{"lang":null},"content":[{"type":"text","text":"// Flip a binary tree \npublic TreeNode invertTree(TreeNode root) {\n}\n\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode(int x) { val = x; }\n * }\n */\n"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"「2. Looking for recursive termination conditions 」"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" 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 :"}]},{"type":"codeblock","attrs":{"lang":null},"content":[{"type":"text","text":"// Flip a binary tree \npublic TreeNode invertTree(TreeNode root) {\n    if(root==null || (root.left ==null && root.right ==null)){\n       return root;\n    }\n}\n"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"「3. The equivalent relation of recursive function 」"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" 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 ~"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/62/629e73062cc04032b14c5cc10e50a54a.jpeg","alt":" The basic algorithm necessary for programmers : Recursion details ","title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" First , You want to flip the root node to 4 The tree of , Need "},{"type":"text","marks":[{"type":"strong"}],"text":"「 Flip its left subtree ( The root node is 2) And right subtree ( The root node is 7)」"},{"type":"text","text":". This is recursive "},{"type":"text","marks":[{"type":"strong"}],"text":"「 Deliver 」"},{"type":"text","text":" The process of "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/24/2417fc5e61de859cfc41f2625779ce22.png","alt":" The basic algorithm necessary for programmers : Recursion details ","title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" so what , The root node is 2 The tree of , It's not a leaf node , You need to continue "},{"type":"text","marks":[{"type":"strong"}],"text":"「 Flip its left subtree ( The root node is 1) And right subtree ( The root node is 3)」"},{"type":"text","text":". Because of the node 1 and 3 All are "},{"type":"text","marks":[{"type":"strong"}],"text":"「 Leaf node 」"},{"type":"text","text":" 了 , So I went back . This is also recursive "},{"type":"text","marks":[{"type":"strong"}],"text":"「 Deliver 」"},{"type":"text","text":" The process of ~"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/2c/2cba5c2df58b2cc4c8f09b949f7a832c.jpeg","alt":" The basic algorithm necessary for programmers : Recursion details ","title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Empathy , The root node is 7 The tree of , It's not a leaf node , You need to flip "},{"type":"text","marks":[{"type":"strong"}],"text":"「 Its left subtree ( The root node is 6) And right subtree ( The root node is 9)」"},{"type":"text","text":". Because of the node 6 and 9 It's all leaf nodes , So it's back ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/91/91948f237d924d47913a5df071222d0f.jpeg","alt":" The basic algorithm necessary for programmers : Recursion details ","title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The left subtree ( The root node is 2) And right subtree ( The root node is 7) It's all flipped over , These steps are "},{"type":"text","marks":[{"type":"strong"}],"text":"「 Return 」"},{"type":"text","text":", That is, the regression process of recursion , The task of flipping the tree is completed ~"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/6e/6e632c462e9a952d4fcbdec20365afd4.png","alt":" The basic algorithm necessary for programmers : Recursion details ","title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" obviously ,"},{"type":"text","marks":[{"type":"strong"}],"text":"「 Recurrence relation 」"},{"type":"text","text":" Namely :"}]},{"type":"codeblock","attrs":{"lang":null},"content":[{"type":"text","text":"invertTree(root)= invertTree(root.left) + invertTree(root.right);\n"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" therefore , It's easy to get the following code :"}]},{"type":"codeblock","attrs":{"lang":null},"content":[{"type":"text","text":"// Flip a binary tree \npublic TreeNode invertTree(TreeNode root) {\n    if(root==null || (root.left ==null && root.right ==null){\n       return root;\n    }\n    // Flip the left subtree \n    TreeNode left = invertTree(root.left);\n    // Flip the right subtree \n    TreeNode right= invertTree(root.right);\n}\n"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" 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 ."}]},{"type":"codeblock","attrs":{"lang":null},"content":[{"type":"text","text":" root.left = right;\n root.right = left;\n"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" therefore ,leetcode This recursive classic topic "},{"type":"text","marks":[{"type":"strong"}],"text":"「 The ultimate solution code 」"},{"type":"text","text":" as follows :"}]},{"type":"codeblock","attrs":{"lang":null},"content":[{"type":"text","text":"class Solution {\n    public TreeNode invertTree(TreeNode root) {\n         if(root==null || (root.left ==null && root.right ==null)){\n           return root;\n         }\n         // Flip the left subtree \n         TreeNode left = invertTree(root.left);\n         // Flip the right subtree \n         TreeNode right= invertTree(root.right);\n         // Left and right subtrees switch positions ~\n         root.left = right;\n         root.right = left;\n         return root;\n    }\n}\n"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Take the ultimate solution code leetcode Submit a , Pass through ~"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/db/dbb6d119362ce9e695d81a8b5ec7900e.png","alt":" The basic algorithm necessary for programmers : Recursion details ","title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":" The problem with recursion "}]},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Too many levels of recursive calls , This leads to a stack overflow problem "}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Recursive repeated calculation , It leads to inefficiency "}]}]}]},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":" Stack overflow problem "}]},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Each function call allocates space in the memory stack , The stack capacity of each process is limited ."}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" When there are too many levels of recursive calls , It will exceed the capacity of the stack , This causes the call stack to overflow ."}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" 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 "}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"「 The code example is as follows :」"}]},{"type":"codeblock","attrs":{"lang":null},"content":[{"type":"text","text":"/**\n *  Recursive stack overflow test \n */\npublic class RecursionTest {\n\n    public static void main(String[] args) {\n        sum(50000);\n    }\n    private static int sum(int n) {\n        if (n <= 1) {\n            return 1;\n        }\n        return sum(n - 1) + n;\n    }\n}\n"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"「 Running results :」"}]},{"type":"codeblock","attrs":{"lang":null},"content":[{"type":"text","text":"Exception in thread \"main\" java.lang.StackOverflowError\n at recursion.RecursionTest.sum(RecursionTest.java:13)\n"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" How to solve this stack overflow problem ? The first thing you need to "},{"type":"text","marks":[{"type":"strong"}],"text":"「 Optimize your recursion 」"},{"type":"text","text":", You really need to call recursively so many times ? If you really need it , Just a little bit "},{"type":"text","marks":[{"type":"strong"}],"text":"「 turn up JVM Stack space memory 」"},{"type":"text","text":", If it still doesn't work , You need to get rid of recursion ,"},{"type":"text","marks":[{"type":"strong"}],"text":"「 Optimize for other solutions 」"},{"type":"text","text":" Slightly ~"}]},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":" Repeat the calculation , It leads to inefficiency of the program "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" 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 ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The vast majority of reader friends , It's easy to think of the following recursive code to solve :"}]},{"type":"codeblock","attrs":{"lang":null},"content":[{"type":"text","text":"class Solution {\n    public int numWays(int n) {\n    if (n == 0){\n       return 1;\n     }\n    if(n <= 2){\n        return n;\n    }\n    return numWays(n-1) + numWays(n-2);\n    }\n}\n"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" But what? , Go to leetcode Submit a , There's a problem , It's beyond the time limit "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/ab/abda71c75fc1293c1f2759cfbfbb2ad2.png","alt":" The basic algorithm necessary for programmers : Recursion details ","title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Why is it overtime ? Where does recursion take ? Draw... First "},{"type":"text","marks":[{"type":"strong"}],"text":"「 Recursive tree 」"},{"type":"text","text":" have a look :"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/56/566a40a9e116deb184077fe31232073e.png","alt":" The basic algorithm necessary for programmers : Recursion details ","title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" To calculate the original problem f(10), We need to calculate the subproblem first f(9) and f(8)"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" And then calculate f(9), We have to work out the subproblem first f(8) and f(7), And so on ."}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Until f(2) and f(1), The recursive tree ends ."}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Let's take a look at the time complexity of recursion ,"},{"type":"text","marks":[{"type":"strong"}],"text":"「 Recursive time complexity = Time to solve a sub problem * Number of sub questions 」"}]},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" A sub question time = f(n-1)+f(n-2), It's an addition operation , So the complexity is  "},{"type":"text","marks":[{"type":"strong"}],"text":"「O(1)」"},{"type":"text","text":";"}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Number of questions = The total number of recursive tree nodes , The summary of recursive trees = 2^n-1, So it's complexity "},{"type":"text","marks":[{"type":"strong"}],"text":"「O(2^n)」"},{"type":"text","text":"."}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" 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 ,"},{"type":"text","marks":[{"type":"strong"}],"text":"「 If n If it's bigger , Overtime is normal 」"},{"type":"text","text":"."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Come back to , You look at this recursive tree , You will find that there is "},{"type":"text","marks":[{"type":"strong"}],"text":"「 A lot of double counting 」"},{"type":"text","text":", 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 !"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"「 that , How to solve this problem ?」"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" 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 "},{"type":"text","marks":[{"type":"strong"}],"text":"「 Memorandum 」"},{"type":"text","text":" 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. "},{"type":"text","marks":[{"type":"strong"}],"text":"「 Solution with memo 」"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Let's take a look "},{"type":"text","marks":[{"type":"strong"}],"text":"「 Recursive solution with memo 」"},{"type":"text","text":" Well ~"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Usually use an array or a hash map Act as this "},{"type":"text","marks":[{"type":"strong"}],"text":"「 Memorandum 」"},{"type":"text","text":"."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" hypothesis f(10) Solution plus "},{"type":"text","marks":[{"type":"strong"}],"text":"「 Memorandum 」"},{"type":"text","text":", Let's draw a recursive tree again :"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"「 First step 」"},{"type":"text","text":",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 :"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/24/24e055469abd833d2bea295b906fd29a.png","alt":" The basic algorithm necessary for programmers : Recursion details ","title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"「 The second step ,」"},{"type":"text","text":" 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 ~"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/78/78c73d347ca88ca81b7933721f9c5afa.png","alt":" The basic algorithm necessary for programmers : Recursion details ","title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"「 The third step ,」"},{"type":"text","text":" 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 ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/c1/c12311d7ce64469e853078f4fe2b2442.png","alt":" The basic algorithm necessary for programmers : Recursion details ","title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" So , Using the memo recursion algorithm , Recursive trees become bare trunks , as follows :"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/54/5453f27a34a96f960ea474d8a2a62227.png","alt":" The basic algorithm necessary for programmers : Recursion details ","title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" belt 「 Memorandum 」 The recursive algorithm of , Number of sub questions = Node number =n, Solving a sub problem is still O(1), therefore "},{"type":"text","marks":[{"type":"strong"}],"text":"「 belt 「 Memorandum 」 The time complexity of recursive algorithm is O(n)」"},{"type":"text","text":". 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 :"}]},{"type":"codeblock","attrs":{"lang":null},"content":[{"type":"text","text":"public class Solution {\n    // Use hash map, Act as a memorandum \n    Map tempMap = new HashMap();\n    public int numWays(int n) {\n        // n = 0  Also calculate 1 Kind of \n        if (n == 0) {\n            return 1;\n        }\n        if (n <= 2) {\n            return n;\n        }\n        // First, judge whether it has been calculated , Let's see if the memo has \n        if (tempMap.containsKey(n)) {\n            // The memo has , That is to say , Go straight back to \n            return tempMap.get(n);\n        } else {\n            //  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 )\n            tempMap.put(n, (numWays(n - 1) + numWays(n - 2)) % 1000000007);\n            return tempMap.get(n);\n        }\n    }\n}\n"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/e4/e4296af607984df697f7f23d9fc0d876.png","alt":" The basic algorithm necessary for programmers : Recursion details ","title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"​"}]},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/e4/e4296af607984df697f7f23d9fc0d876.png","alt":" The basic algorithm necessary for programmers : Recursion details ","title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":" At the end "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Now that you can see it, this article is helpful to you , Can Xiaobian ask for a little praise for you ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":" Extended learning reading "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"link","attrs":{"href":"https://blog.csdn.net/javachengzi/article/details/109516189","title":null},"content":[{"type":"text","text":" Still worrying about algorithms ? So you haven't seen this one yet Github On 70k Star Notes "}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" video :"},{"type":"link","attrs":{"href":"https://www.bilibili.com/video/BV1WA411j7go/","title":null},"content":[{"type":"text","text":" Brute force recursive algorithm "}]}]},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":" After reading three things ️"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"========"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" If you think this is helpful for you , I'd like to invite you to do me three little favors :"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" give the thumbs-up , forward , There's your 『 Praise and comment 』, That's what motivates me to create ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Official account 『 Java Doudi 』, Share original knowledge from time to time ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" At the same time, we can look forward to the following articles ing"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}}]}

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

Scroll to Top