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

Scroll to Top