## 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 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 ：

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

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

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

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 ~

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

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

Why is it overtime ？ Where does recursion take ？ Draw... First **「 Recursive tree 」** have a look ：

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

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

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 ：

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