Basic algorithms programmers must have: recursive detailed solution

preface

Recursion is a very important algorithmic idea that you need to master whether you’re doing front-end or back-end development. In everyday work, counting folder sizes, parsing XML files, and so on, recursive algorithms are needed. It’s so basic and so important, which is why in interviews, interviewers often ask us to write recursive algorithms by hand. In this article, we will learn about recursive algorithms

What is recursion?
Recursion
Recursion versus stack
Recursive application scenarios
Recursively
Leetcode case study
Possible problems with recursion and solutions

Github address, thanks to every Star

Github.com/whx123/Java…

Public number: a boy picking up snails

What is recursion?

Recursion, in computer science, is a method of solving a problem by repeatedly breaking it down into subproblems of the same kind. Simply put, recursion manifests as a function calling the function itself. I saw an example of metaphorical recursion in Zhihu, which I think is very vivid. Let’s take a look:

The best metaphor for recursion is to look it up in a dictionary. The dictionaries we use are inherently recursive, requiring the use of more words in order to explain one word. When you look up a word, I found some words in the explanation of the word still do not understand, then you begin to look up the second word, however, there are still not understand of the words in the second word, then look up the third word, so check, until there is a word of explanation is that you can fully understand, so the recursive came to an end, and then you began to retreat, one by one checked before understand every word, in the end, You see what the original word means.

To test the waters, take a look at an example of recursive code like this:

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

Recursion

In fact, recursion has two distinctive features, termination conditions and self calls:

Self call: the original problem can be decomposed into sub-problems, and the solution method of the sub-problem and the original problem is the same, that is, they call the same function.
Termination condition: Recursion must have a termination condition, that is, it cannot call itself in an infinite loop.

Combined with the above demo code examples, look at the characteristics of recursion:

Recursion versus stack

In fact, the process of recursion can be understood as the process of going in and out of the stack. This metaphor is just for the convenience of readers to better understand recursion. The stack diagram for sum (n=3) is as follows:

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

When calculating sum (5), sum (5) is first pushed onto the stack, and then the original problem sum (5) is split into subproblems sum (4), and then pushed onto the stack until the termination condition sum (n=1) =1.
Sum (1) is out of the stack, sum (2) is out of the stack, and then sum (3).
Finally,sum (1) is last-in, first-out, and sum (5) is last-in, last-out

The classic application scenario of recursion

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

Factorial problem
Binary tree depth
Hannotta problem
Fibonacci numbers
Quicksort, merge sort (divide-and-conquer algorithm also uses recursion)
Walk through the file, parse the XML file

Recursively

There are generally three steps to solve recursion problems, which are:

The first step is to define the function function
The second step is to find recursive termination conditions
The second step is to deduce the equivalent relation of recursive function

This recursive solution is a little abstract, so let’s take the factorial recursion example

1. Define function functions

Define the function, that is, what does your function do, what does it do, in other words, you have to know what the recursion problem is? For example, if you need to solve the factorial problem, the function defined is n factorial, as follows:

// factorial (n is a number greater than 0) int factorial (int n){}Copy the code

2. Look for recursive termination conditions

A typical feature of recursion is that it must have a termination condition, that is, it cannot call itself in an infinite loop. So, when we use recursive thinking to solve the problem, we need to find what the recursive termination condition is. For example, in the factorial problem, when n=1, instead of recursing further, we can break out of the loop, and n=1 can be used as a termination condition for recursion, as follows:

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

3. Equivalent relations of recursive functions

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

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

Note that not all recursive functions are equivalent to factorials, which can be derived at once. We need more contact, more accumulation, more thinking, more practice recursion problems drop ~

Leetcode case study

Let’s analyze a classic problem of Leetcode recursion

The original link is here: leetcode-cn.com/problems/in…

Title: Flipping a binary tree.

Input:

4 / \ 27 / \ / \ 1 3 6 9Copy the code

Output:

4 / \ 7 2 / \ / 9 6 3 1Copy the code

We follow the above recursive solution to the three plate axe:

1. Define function functions

The function function (i.e., the recursion problem is), gives a tree and then flips it, so the function can be defined as:

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; }} * * /Copy the code

2. Look for recursive termination conditions

When does the tree not have to flip? When the current node is null or a leaf node. Therefore, adding the termination condition is:

/ / flip a binary tree public TreeNode invertTree TreeNode (root) {if (root = = null | | (root) left = = null && root. The right = = null)) {return root; }}Copy the code

3. Equivalent relations of recursive functions

If you want to flip a tree, can you split it into subproblems and flip its left and right subtrees? Can the subproblem of flipping its left subtree be split into flipping its left subtree of its left subtree and its right subtree of its left subtree? Then flip it all the way to the leaf node. Well, look at the picture to understand

First of all, if you want to flip the tree with root 4, you need toFlip its left subtree (root 2) and right subtree (root 7). This is recursiverecursiveIn the process!

And then, for a tree with root 2, which is not a leaf, you need to continue flipping its left subtree (root 1) and right subtree (root 3). Since nodes 1 and 3 are leaf nodes, they return. This is also a recursive recursive process

Similarly, a tree with root 7 is not a leaf, so you need to flip its left subtree (root 6) and right subtree (root 9). Since nodes 6 and 9 are leaf nodes, they return as well.

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

Obviously, the recursive relation is:

InvertTree (root) = invertTree (root.left) + invertTree (root.right);Copy the code

As a result, it is easy to get the following code:

/ / flip a binary tree public TreeNode invertTree TreeNode (root) {if (root = = null | | (root) left = = null && root. The right = = null) {return root; TreeNode left = invertTree(root.left); TreeNode right= invertTree(root.right); }Copy the code

There is one area of code that needs to be noted here. After flipping the left and right subtrees of a tree, we also need to swap the reference positions of the left and right subtrees.

 root.left = right;
 root.right = left;
Copy the code

Thus, the ultimate solution to Leetcode’s recursive classic is as follows:

class Solution { public TreeNode invertTree(TreeNode root) { if(root==null || (root.left ==null && root.right ==null)){ return root; TreeNode left = invertTree(root.left); TreeNode right= invertTree(root.right); ~ root.left = right; root.right = left; return root; }}Copy the code

Submit the final solution to LeetCode

The problem with recursion

There are too many levels of recursive calls, causing stack overflow problems
Recursive double-counting, resulting in inefficiency

Stack overflow problem

Each function call allocates space in the memory stack, and the stack size of each process is limited.
When there are too many levels of recursive calls, the stack size is exceeded, resulting in call stack overflow.
In fact, as we discussed in the previous section, recursion is similar to going off the stack and onto the stack. If you recurse too many times, the depth of the stack becomes deeper and eventually the stack becomes insufficient

Example code is as follows:

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; }}Copy the code

Running results:

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

How to solve this stack overflow problem? First, you need to optimize your recursion. Do you really need to recurse so many times? If you really need to, you need to tweak the stack space of the JVM a little bit. If that doesn’t work, you need to discard recursion and optimize for another solution

Double calculation, resulting in inefficient programs

Let’s look at the classic frog jumping problem: a frog can jump up one step at a time, or two steps at a time. Find out how many ways the frog can jump up n steps.

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

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

However, go to Leetcode to submit, there is a problem, beyond the time limit

Why is it over time? What’s the recursion time? Let’s draw the recursion tree:

To compute the original problem f(10), we need to compute the subproblems F (9) and f(8) first.
And then you have to compute f(9), and then you have to compute the subproblems f(8) and f(7), and so on.
All the way to f(2) and f(1), the recursion tree ends.

So let’s look at the time of this recursion, which is equal to the time to solve one subproblem times the number of subproblems

A subproblem time = F (n-1) + F (n-2), which is an addition operation, so the complexity is O(1);
The number of problems is equal to the number of nodes in the recursion tree, and the summation point of the recursion tree is equal to 2 to the n minus 1, so it’s O(2 to the n).

So, if the frog jumps, the time complexity of the recursive solution is O(1) * O(2^n) = O(2^n), which is exponential and explodes. If n is large, timeouts are normal.

If you go back and look at the recursion tree, you’ll see a lot of double counting, like f (8) being double counted twice, f (7) being double counted three times… So what makes this recursive algorithm inefficient is that there’s a lot of double counting!

So, how to solve this problem?

Since there is a lot of repeated calculation, so we can first save the calculated answer, that is, make a memo, wait until the next need, go to the memo to check, if there is, just take it directly, the memo is not calculated again, then you can save the time of repeated calculation! That’s the solution with the memo

Let’s look at recursion with memo

You typically use an array or hash map as the memo.

Assuming f(10) is solved plus memo, let’s draw the recursion tree again:

In the first step, f(10) = f(9) + f(8), both f(9) and f(8) need to be calculated and then added to the memo as follows:

Second step,f (9) = f(8) + f(7),f (8) = F (7) + f(6), because f(8) has been in the memo, so it can be omitted,f (7),f (6) need to be calculated and added to the memo ~

The third step,F (8) = f(7) + f(6), it is found that f(8), F (7),f (6) are all in the memo, so they can be cut.

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

For recursion algorithm with “memo”, the number of subproblems = number of tree nodes = N, and solving a subproblem is still O(1), so the time complexity of recursion algorithm with “memo” is O(n). Next, we use a recursive algorithm with “memo” to solve the frog jump problem timeout problem. The code is as follows:

Public class Solution {// use HashMap to act as memo map <Integer, Integer> tempMap = new HashMap(); Public int numWays(int n) {// if (n == 0) {return 1; } if (n <= 2) { return n; If (tempmap.containsKey (n)) {if (tempmap.containsKey (n)) {return tempmap.get (n); } else {// The memo has not been calculated, performs a recursive calculation, and saves the result to the memo map, Mod 1000000007 tempmap. put(n, (numWays(n-1) + numWays(n-2)) % 1000000007); return tempMap.get(n); }}}Copy the code

Go to Leetcode to submit it, as shown in the picture, stable:

Are there any other solutions to this problem? Just a recursion with a memo, right? Actually, you can do it with dynamic programming

How to solve the problem with the idea of dynamic programming algorithm? We’ll continue next time. Thanks for reading

Reference and thanks

[article learn recursive problem solving] (mp.weixin.qq.com/s/Hew44D8rd…).
“Dynamic programming, rounding] (mp.weixin.qq.com/s/1V3aHVonW…

More dry