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

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

Recursive “original meaning”, is the original problem can be split into the same kind and easier to solve the problem of child, namely “the original problem and the problem can be expressed in the same function relation. Recursive function equivalence relation, this step is equivalent to looking for the original problem and son relationship, how to use a formula to express clearly the function”. 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 and 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 link to the original question is here: leetcode-cn.com/problems/in… ❞

“Title:” Reverse 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 function”

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. Search 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, if you want to flip a tree with root 4, you need to “flip its left subtree (root 2) and right subtree (root 7).” That’s how recursion works

Then, for a tree with root 2, which is not a leaf, you need to “flip its left subtree (root 1) and right subtree (root 3)”. Since nodes 1 and 3 are “leaf nodes”, they return. This is also the process of recursion

Similarly, a tree with root 7 is not a leaf, and 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 both the left subtree (root node 2) and the right subtree (root node 7) are flipped, these steps “return”, i.e., 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 code” for 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 Result:”

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, “increase the STACK space of the JVM” a little. If that doesn’t work, then 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.

Let’s first look at the time complexity of this recursion, “recursive time complexity = number of subproblems in time to solve a subproblem” *

  • A subproblem time = F (n-1) + F (n-2), which is an addition operation, so complexity is “O(1)”;

  • The number of problems = the total number of nodes in the recursion tree, and the conclusion point of the recursion tree = 2n-1, so the complexity is “O(2n)”.

So, frog jump, recursive solution time complexity = O(1) * O(2^n) = O(2^n), is exponential, explosive growth, “if n is large, timeout is very normal”.

Going back and looking at the recursion tree, you will see that there is “a lot of double counting”, such as f (8) being counted twice, f (7) being counted three times… So what makes this recursive algorithm inefficient is that there’s a lot of double counting!

“So, how do you 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, first go to the “memo” 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 a memo.

Let’s take a look at “recursion with memo”

You typically use an array or hash map to act as this “memo.”

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

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:

“Step 2,” f(9) = f(8) + f(7),f (8) = f(7) + f(6), because f(8) is already in the memo, so it can be omitted,f (7),f (6) need to be calculated and added to the memo ~

“Step 3,” f(8) = f(7) + f(6), find 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 the recursive algorithm with “memo”, the number of subproblems = number of tree nodes = N, and solving a subproblem is still O(1). Therefore, the time complexity of the recursive 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: