“🌟🌟🌟🌟🌟“

“Taste: Hair blood wang“

“Cooking time: 10min“

This article has been featured on Github github.com/Geekhyt, thanks to Star.

Data structures and algorithms is the third article in the series. If you haven’t seen the first two articles, please follow the links below.

  • How does the front end handle data structures and algorithms
  • Time and space complexity analysis of JavaScript algorithm

In this article we are going to talk about recursion, why is the third bullet recursive?

Because many algorithm ideas are based on recursion, whether DFS, tree traversal, divide-and-conquer algorithm, dynamic programming, etc., are the application of recursion ideas. Learned to use recursion to solve the problem of this way of thinking, and then to learn other algorithm ideas, is undoubtedly twice the result with half the effort.

The nature of recursion

“Helpless flowers fall, deja vu swallows return.“

Recursion, the process of going is called “recursion”, and the process of coming back is called “return”.

Exploring the nature of recursion begins with the nature of computer languages.

The essence of computer language is assembly language, which is characterized by no loop nesting. We usually use high-level language to write if.. else.. At the level of actual machine instructions, for/while is a simple address jump to a specific instruction location, similar to a GOto statement.

Machines always have no temperature. When you were young, you must have looked up Chinese characters in Xinhua Dictionary. If you want to look up the explanation of the word, there are also unknown words. It is necessary to then check the second word, unfortunately, in the explanation of the second word, also do not know the word, it is necessary to then check the third word. Until there is one word that we can fully understand, the recursion ends. Then we started to back up, picking through each word we had looked up, and finally, we figured out the first word we wanted to look up.

So let’s do a little bit of recursion with one more piece of code.

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

Factorial is a function that implements the factorial. Let’s see the recursion in terms of factorial f of 6.


F (6) = n * f(5), so F (6) needs to be disassembled into f(5) sub-problem for solving, and so on, f(5) = n * f(4), which also needs to be further disassembled… All the way to f(1), “This is recursion.” After f(1) is solved, f(2)…. can be solved in turn F (n) is finally solved, “This is the return process.”

As can be seen from the above two examples, recursion is nothing more than disassembling the problem into sub-problems with the same solution idea until the sub-problems can not be disassembled at last. This process is called “recursion”. After solving the smallest solvable sub-problem, the initial problem is naturally solved in the process of “returning”.

Now that we understand the nature of recursion, we need to remember that there are three conditions for recursion before we use recursion:

1. The problem can be broken down into several sub-problems

2. The solution method of the problem and subproblem is exactly the same

3. Recursive termination conditions

“Knock on the blackboard and take notes!“

LeetCode bo

Let’s practice with a LeetCode problem.

Solve the Fibonacci sequence, which starts with 0 and 1, and each subsequent digit is the sum of the previous two, i.e. :

F (0) = 0, F (1) = 1, F (N) = F (N - 1) + F (N - 2), where N > 1.Copy the code

Given N, compute F(N).


The recursion tree is shown in the figure above. To compute f(5), first compute the subproblems f(4) and f(3). To compute f(4), first compute the subproblems F (3) and f(2)… And so on, when you finally get to f(0) or f(1), you know the answer, and then you return the answer.

After the above analysis, meet the three conditions of recursion, began to strip code.

The recursive method

const fib = function(n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
} Copy the code

Or show off your skills like this:

const fib = n= > n <= 0 ? 0 : n == 1 ? 1: fib(n - 2) + fib(n - 1);
Copy the code

We’re not done yet, so remember to get in the habit of doing complexity analysis on the algorithms you write. This section is covered in the JavaScript algorithm time and space complexity analysis column. If you haven’t seen it, please click the link.

Complexity analysis

  • The space complexity is order n.
  • Time complexity O(2^n)

Total time = Number of subproblems * Time required to solve a subproblem

  • The number of subproblems is the total number of nodes in the recursion tree 2 to the n
  • The time required to solve a subproblem because there is only one addition operationfib(n-1) + fib(n-2), so the time to solve a subproblem isO(1)

Multiply them together, and you get O(2^n), exponential, cracked.

It would be a mistake to write only one solution in an interview.

In fact, this problem can be solved by using dynamic programming or golden ratio formula. If you want to explain dynamic programming clearly, it will take a long time, and a follow-up column will be introduced in detail. Don’t worry if you don’t understand it.

(I chose this problem in order to give you an idea of recursion.)

Dynamic programming solution

While recursion is top-down (see recursion tree above), dynamic programming is bottom-up, changing recursion to iteration. In order to reduce space consumption, only two values are stored, which is the optimal solution of dynamic programming.

  • Time complexity O(n)
  • Space complexity O(1)
const fib = function(n) {
    if (n == 0) {
        return 0;
    }
    let a1 = 0;
 let a2 = 1;  for (let i = 1; i < n; i++) {  [a1, a2] = [a2, a1 + a2];  }  return a2; } Copy the code

Golden section specific term formula solution

  • Time complexity O(logn)
  • Space complexity O(1)
const fib = function(n) {
    return (Math.pow((1 + Math.sqrt(5)) /2, n) - Math.pow((1 - Math.sqrt(5)) /2, n)) / Math.sqrt(5);
}
Copy the code

Otherwise, you can use matrix equations, which I’m not going to expand here.

Going back to recursion, the biggest pitfall in learning recursion is human recursion. It is difficult for the human brain to think clearly about the whole process of "recursion" and "return" without error. But computers are good at doing repetitive things, so we don't have to jump into the details and use the idea of mathematical induction to abstract it down to a recursive formula. Trust it to accomplish this task and leave the rest to the computer.

If you have to explore the details of it, challenge the brain stack, then you will only fall into it, even doubt life. The south wall is not easy to hit, should turn back.

When you look into an abyss, the abyss looks into you.

Past popular columns

  • 20+Vue interview questions
  • A dozen more Webpack interview questions
  • Want to enter the big factory must know Web security issues
  • HTTP questions that interviewers have had to deal with over the years

❤️ Love triple punch

1. Please give me a “like” when you see this. Your “like” is the motivation for my creation.

2. Pay attention to the front canteen of the public account, “your front canteen, remember to eat on time”!

3. This article has been included in the front canteen Github github.com/Geekhyt, for a small Star, thanks to Star.